DotNet Reference

DotNet Reference

SimpleMinCostFlowProgram.cs
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // """From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1."""
15 // [START program]
16 using System;
17 using Google.OrTools.Graph;
18 
20 {
21  static void Main()
22  {
23  // [START data]
24  // Define four parallel arrays: sources, destinations, capacities, and unit costs
25  // between each pair. For instance, the arc from node 0 to node 1 has a
26  // capacity of 15.
27  // Problem taken From Taha's 'Introduction to Operations Research',
28  // example 6.4-2.
29  int[] startNodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
30  int[] endNodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
31  int[] capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
32  int[] unitCosts = {4, 4, 2, 2, 6, 1, 3, 2, 3};
33 
34  // Define an array of supplies at each node.
35  int[] supplies = {20, 0, 0, -5, -15};
36  // [END data]
37 
38  // [START constraints]
39  // Instantiate a SimpleMinCostFlow solver.
40  MinCostFlow minCostFlow = new MinCostFlow();
41 
42  // Add each arc.
43  for (int i = 0; i < startNodes.Length; ++i)
44  {
45  int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],
46  capacities[i], unitCosts[i]);
47  if (arc != i) throw new Exception("Internal error");
48  }
49 
50  // Add node supplies.
51  for (int i = 0; i < supplies.Length; ++i)
52  {
53  minCostFlow.SetNodeSupply(i, supplies[i]);
54  }
55 
56  // [END constraints]
57 
58  // [START solve]
59  // Find the min cost flow.
60  MinCostFlow.Status solveStatus = minCostFlow.Solve();
61  // [END solve]
62 
63  // [START print_solution]
64  if (solveStatus == MinCostFlow.Status.OPTIMAL)
65  {
66  Console.WriteLine("Minimum cost: " + minCostFlow.OptimalCost());
67  Console.WriteLine("");
68  Console.WriteLine(" Edge Flow / Capacity Cost");
69  for (int i = 0; i < minCostFlow.NumArcs(); ++i)
70  {
71  long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
72  Console.WriteLine(minCostFlow.Tail(i) + " -> " +
73  minCostFlow.Head(i) + " " +
74  string.Format("{0,3}", minCostFlow.Flow(i)) + " / " +
75  string.Format ("{0,3}", minCostFlow.Capacity(i)) + " " +
76  string.Format ("{0,3}", cost));
77  }
78  }
79  else
80  {
81  Console.WriteLine("Solving the min cost flow problem failed. Solver status: " +
82  solveStatus);
83  }
84  // [END print_solution]
85  }
86 }
87 // [END program]
int Head(int arc)
Definition: MinCostFlow.cs:95
Status
int NumArcs()
Definition: MinCostFlow.cs:85
long Flow(int arc)
Definition: MinCostFlow.cs:75
MinCostFlowBase.Status Solve()
Definition: MinCostFlow.cs:55
long Capacity(int arc)
Definition: MinCostFlow.cs:100
long OptimalCost()
Definition: MinCostFlow.cs:65
long UnitCost(int arc)
Definition: MinCostFlow.cs:110
Definition: MinCostFlow.cs:13
int Tail(int arc)
Definition: MinCostFlow.cs:90
void SetNodeSupply(int node, long supply)
Definition: MinCostFlow.cs:51
int AddArcWithCapacityAndUnitCost(int tail, int head, long capacity, long unit_cost)
Definition: MinCostFlow.cs:46