linearprogramming_maxflownetwork_ortools.cs

using System;
using Google.OrTools.LinearSolver;


// Max-flow algorithm example


// Capacities Graph Network (first row should correspond to S, last to T)
int[,] capacitiesGraph = new int[6, 6]
{
  {0, 18, 0, 15, 0, 0},
  {0, 0, 9, 2, 10, 0},
  {0, 0, 0, 0, 0, 13},
  {0, 0, 0, 0, 3, 0},
  {0, 0, 5, 0, 0, 12},
  {0, 0, 0, 0, 0, 0},
};


// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
    return;
}


// Function to label Nodes
String NodeLabeler(int number, bool isCaps, int length)
{
    if (number == 0)
    {
        return "S";
    } else if (number == length-1)
    {
        return "T";
    } else
    {
        Char c = (Char)((isCaps ? 65 : 97) + (number - 1));
        return c.ToString();
    }
}


// Create list where variables will be stored
List<Variable> Vars = new List<Variable>();

// Create list of vertices
List<String> vertexList = new List<String>();
for (int i = 0; i<capacitiesGraph.GetLength(0); i++)
{
    vertexList.Add(NodeLabeler(i, true, capacitiesGraph.GetLength(0)));
}


// Creating variables
for (int i=0; i<capacitiesGraph.GetLength(0); i++)
{
    for (int j=0; j < capacitiesGraph.GetLength(1); j++)
    {
        if (capacitiesGraph[i,j] > 0)
        {
            Vars.Add(solver.MakeIntVar(0, double.PositiveInfinity, NodeLabeler(i, true, capacitiesGraph.GetLength(0)) + "_" + NodeLabeler(j, true, capacitiesGraph.GetLength(0))));
        }
    }
}

// List of variable names
List<String> varNames = new List<string>();
foreach (Variable var in Vars)
{
    varNames.Add(var.Name());
}



// Function that receives an edge (example receives "S_A" and returns 10)
int GetEdgeCapacity(String edge, int[,] capacities, List<String> vertexList)
{
    String vertexFrom = edge.Substring(0, 1);
    String vertexTo = edge.Substring(edge.Length - 1, 1);
    int vertexFromIdx = vertexList.IndexOf(vertexFrom);
    int vertexToIdx = vertexList.IndexOf(vertexTo);
    return capacities[vertexFromIdx, vertexToIdx];

}


// Adding constraints conservation of flow
List<String> flowIn = new List<string>();
List<String> flowOut = new List<string>();
foreach (String v in vertexList)
{
    flowIn.Clear();
    flowOut.Clear();
    foreach (String e in varNames)
    {
        if (e.Substring(e.Length-1,1) == v)
        {
            flowIn.Add(e);
        }
        if (e.Substring(0,1) == v)
        {
            flowOut.Add(e);
        }
    }
    if (flowIn.Count()>0 && flowOut.Count() > 0)
    {
        LinearExpr sumFlowIn = new LinearExpr();
        LinearExpr sumFlowOut = new LinearExpr();
        foreach (String e in flowIn)
        {
            sumFlowIn += Vars[varNames.IndexOf(e)];
        }
        foreach (String e in flowOut)
        {
            sumFlowOut += Vars[varNames.IndexOf(e)];
        }
        solver.Add(sumFlowIn == sumFlowOut);

    }
}

// Adding constraints capacities of flow
foreach (String e in varNames)
{
    int capEdge = GetEdgeCapacity(e, capacitiesGraph, vertexList);
    Console.WriteLine(e + " " + capEdge);
    solver.Add(Vars[varNames.IndexOf(e)] <= capEdge);

}


// Function to get the edges from Source
List<String> EdgesFromSource(List<String> edges)
{
    List<String> edgesFromSource = new List<String>();  
    foreach (String edge in edges)
    {
        if (edge.Substring(0,1) == "S")
        {
            edgesFromSource.Add(edge);
        }
    }
    return edgesFromSource;
}


// Defining cost function
LinearExpr costFunction = new LinearExpr();
List<String> edgesFromSource = EdgesFromSource(varNames);

foreach (String edge in edgesFromSource)
{
    costFunction += Vars[varNames.IndexOf(edge)];
}


solver.Maximize(costFunction);

Solver.ResultStatus resultStatus = solver.Solve();


// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("The problem does not have an optimal solution!");
    return;
}
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
foreach (Variable v in Vars)
{
    Console.WriteLine(v.Name() + "=" + v.SolutionValue());
}