最小コストのフロー ソルバーを使用して、割り当ての問題の特殊なケースを解くことができます。
実際、最小コストのフローでは多くの場合、MIP または CP-SAT ソルバーよりも速くソリューションが返されることがあります。ただし、MIP と CP-SAT は最小コストフローよりも多くの問題を解決できるため、ほとんどの場合、MIP または CP-SAT が最適な選択肢となります。
以下のセクションでは、最小コストのフロー ソルバーを使用して次の割り当て問題を解決する Python プログラムを示します。
線形割り当ての例
このセクションでは、線形割り当て解法で説明した例を、最小コストフローの問題として解決する方法について説明します。
ライブラリのインポート
次のコードは、必要なライブラリをインポートします。
Python
from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
ソルバーを宣言する
次のコードは、最小コストのフロー ソルバーを作成します。
Python
# Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
データを作成する
この問題のフロー図は、コスト マトリックスの二部分グラフで構成され(わずかに異なる例については、割り当ての概要を参照)、ソースとシンクが追加されています。
データには、問題の開始ノード、終了ノード、容量、費用に対応する次の 4 つの配列が含まれています。各配列の長さはグラフ内の円弧の数になります。
Python
# Define the directed graph for the flow. start_nodes = ( [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8] ) end_nodes = ( [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9] ) capacities = ( [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] ) costs = ( [0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0] ) source = 0 sink = 9 tasks = 4 supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
C++
// Define four parallel arrays: sources, destinations, capacities, // and unit costs between each pair. For instance, the arc from node 0 // to node 1 has a capacity of 15. const std::vector<int64_t> start_nodes = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; const std::vector<int64_t> end_nodes = {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; const std::vector<int64_t> capacities = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = {0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 9; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
Java
// Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; int[] endNodes = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; int[] capacities = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
C#
// Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 }; int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 }; int[] capacities = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0 }; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
データの設定方法を明確にするため、各配列は次の 3 つのサブ配列に分割されています。
- 最初の配列は、ソースから導き出す円弧に対応しています。
- 2 つ目の配列は、ワーカーとタスクの間の円弧に対応しています。
costs
の場合、これは単なるコスト行列(線形割り当てソルバーで使用)で、ベクトルに平坦化されます。 - 3 つ目の配列はシンクにつながる円弧に対応しています。
このデータには、各ノードでの電力供給を示すベクトル supplies
も含まれています。
最小費用フローの問題が割り当ての問題を表す仕組み
上記の最小費用フローの問題は、割り当ての問題をどのように表しますか。まず、すべてのアークの容量が 1 であるため、ソースで 4 を供給すると、ワーカーにつながる 4 つのアークのそれぞれが 1 のフローになります。
次に、flow-in-equals-flow-out 条件で、各ワーカーからのフローが強制的に 1 になります。可能であれば、ソルバーはそのフローを各ワーカーから発生する最小コストアークに向けます。ただし、ソルバーで 2 つの異なるワーカーから 1 つのタスクにフローを指示することはできません。その場合、そのタスクで 2 つのフローが組み合わされ、容量 1 の単一のアークをタスクからシンクに送信できません。つまり、解法は割り当ての問題で要求されるように、タスクを 1 つのワーカーにのみ割り当てることができます。
最後に、「flow-in-equals-flow-out」条件で各タスクの流出が 1 になるようにします。したがって、各タスクはなんらかのワーカーによって実行されます。
グラフと制約を作成する
次のコードは、グラフと制約を作成します。
Python
# Add each arc. for i in range(len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(len(supplies)): smcf.set_node_supply(i, supplies[i])
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); }
ソルバーを呼び出す
次のコードは、ソルバーを呼び出して解を表示します。
Python
# Find the minimum cost flow between node 0 and node 10. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
このソリューションは、ワーカーとタスクの間のアークで構成されます。これらのアークは、ソルバーによって 1 のフローが割り当てられたものです。(ソースまたはシンクに接続されているアークはソリューションには含まれません)。
このプログラムは各円弧にフロー 1 があるかどうかを確認します。存在する場合、割り当てのワーカーとタスクに対応する円弧の Tail
(開始ノード)と Head
(終了ノード)を出力します。
プログラムの出力
Python
if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or into sink. if smcf.tail(arc) != source and smcf.head(arc) != sink: # Arcs in the solution have a flow value of 1. Their start and end nodes # give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}")
C++
if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; }
Java
if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); }
プログラムの出力は以下のとおりです。
Total cost = 265 Worker 1 assigned to task 8. Cost = 70 Worker 2 assigned to task 7. Cost = 55 Worker 3 assigned to task 6. Cost = 95 Worker 4 assigned to task 5. Cost = 45 Time = 0.000245 seconds
結果は、線形割り当てソルバーの場合と同じです(ワーカーとコストの数が異なります)。線形割り当てソルバーは最小コストフローよりわずかに速く、0.000458 秒に対して 0.000147 秒となっています。
プログラム全体
プログラム全体を以下に示します。
Python
"""Linear assignment example.""" from ortools.graph.python import min_cost_flow def main(): """Solving an Assignment Problem with MinCostFlow.""" # Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow() # Define the directed graph for the flow. start_nodes = ( [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8] ) end_nodes = ( [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9] ) capacities = ( [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] ) costs = ( [0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0] ) source = 0 sink = 9 tasks = 4 supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks] # Add each arc. for i in range(len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(len(supplies)): smcf.set_node_supply(i, supplies[i]) # Find the minimum cost flow between node 0 and node 10. status = smcf.solve() if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or into sink. if smcf.tail(arc) != source and smcf.head(arc) != sink: # Arcs in the solution have a flow value of 1. Their start and end nodes # give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}") if __name__ == "__main__": main()
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h" namespace operations_research { // MinCostFlow simple interface example. void AssignmentMinFlow() { // Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow; // Define four parallel arrays: sources, destinations, capacities, // and unit costs between each pair. For instance, the arc from node 0 // to node 1 has a capacity of 15. const std::vector<int64_t> start_nodes = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; const std::vector<int64_t> end_nodes = {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; const std::vector<int64_t> capacities = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = {0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 9; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. int status = min_cost_flow.Solve(); if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; } } } // namespace operations_research int main() { operations_research::AssignmentMinFlow(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase; /** Minimal Assignment Min Flow. */ public class AssignmentMinFlow { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8}; int[] endNodes = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9}; int[] capacities = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0}; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve(); if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private AssignmentMinFlow() {} }
C#
using System; using Google.OrTools.Graph; public class AssignmentMinFlow { static void Main() { // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 }; int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 }; int[] capacities = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0 }; int source = 0; int sink = 9; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve(); if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); } } }
ワーカーのチームでの割り当て
このセクションでは、より一般的な割り当ての問題を示します。この問題では 6 人の従業員が 2 つのチームに 分割されています。問題は、ワークロードがチーム間で均等に分散されるように、4 つのタスクをワーカーに割り当てることです。つまり、各チームが 2 つのタスクを実行することになります。
この問題に対する MIP ソルバー ソリューションについては、ワーカーのチームによる割り当てをご覧ください。
以降のセクションでは、最小コストのフロー ソルバーを使用して問題を解決するプログラムについて説明します。
ライブラリのインポート
次のコードは、必要なライブラリをインポートします。
Python
from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
ソルバーを宣言する
次のコードは、最小コストのフロー ソルバーを作成します。
Python
smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
データを作成する
次のコードは、プログラムのデータを作成します。
Python
# Define the directed graph for the flow. team_a = [1, 3, 5] team_b = [2, 4, 6] start_nodes = ( # fmt: off [0, 0] + [11, 11, 11] + [12, 12, 12] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] + [7, 8, 9, 10] # fmt: on ) end_nodes = ( # fmt: off [11, 12] + team_a + team_b + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] + [13, 13, 13, 13] # fmt: on ) capacities = ( # fmt: off [2, 2] + [1, 1, 1] + [1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] # fmt: on ) costs = ( # fmt: off [0, 0] + [0, 0, 0] + [0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95] + [0, 0, 0, 0] # fmt: on ) source = 0 sink = 13 tasks = 4 # Define an array of supplies at each node. supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
C++
// Define the directed graph for the flow. const std::vector<int64_t> team_A = {1, 3, 5}; const std::vector<int64_t> team_B = {2, 4, 6}; const std::vector<int64_t> start_nodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; const std::vector<int64_t> end_nodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; const std::vector<int64_t> capacities = {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 13; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
Java
// Define the directed graph for the flow. // int[] teamA = new int[] {1, 3, 5}; // int[] teamB = new int[] {2, 4, 6}; int[] startNodes = new int[] {0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; int[] capacities = new int[] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
C#
// Define the directed graph for the flow. int[] teamA = { 1, 3, 5 }; int[] teamB = { 2, 4, 6 }; // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10 }; int[] endNodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13 }; int[] capacities = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0 }; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
ワーカーはノード 1 ~ 6 に対応しています。チーム A はワーカー 1、3、5 で構成され、チーム B はワーカー 2、4、6 で構成されています。タスクには 7 ~ 10 の番号が付いています。
ソースとワーカーの間に、11 と 12 という 2 つの新しいノードがあります。ノード 11 はチーム A のノードに接続され、ノード 12 はチーム B のノードに接続され、容量は 1 のアークになります。以下のグラフは、ソースからワーカーへのノードとアークのみを示しています。
ワークロードを分散するための鍵は、ソース 0 が容量 2 のアークによってノード 11 と 12 に接続されていることです。つまり、ノード 11 と 12(したがってチーム A と B)の最大フローは 2 です。そのため、各チームは 2 つまでのタスクを実施できます。
制約を作成する
Python
# Add each arc. for i in range(0, len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(0, len(supplies)): smcf.set_node_supply(i, supplies[i])
C++
// Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); }
Java
// Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); }
C#
// Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); }
ソルバーを呼び出す
Python
# Find the minimum cost flow between node 0 and node 10. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
プログラムの出力
Python
if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or intermediate, or into sink. if ( smcf.tail(arc) != source and smcf.tail(arc) != 11 and smcf.tail(arc) != 12 and smcf.head(arc) != sink ): # Arcs in the solution will have a flow value of 1. # There start and end nodes give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}")
C++
if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into // sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 && min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; }
Java
if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11 && minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); }
C#
if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); }
プログラムの出力を以下に示します。
Total cost = 250 Worker 1 assigned to task 9. Cost = 75 Worker 2 assigned to task 7. Cost = 35 Worker 5 assigned to task 10. Cost = 75 Worker 6 assigned to task 8. Cost = 65 Time = 0.00031 seconds
チーム A にはタスク 9 とタスク 10 が割り当てられ、チーム B にはタスク 7 とタスク 8 が割り当てられます。
この問題では、最小コストのフロー ソルバーは約 0.006 秒かかる MIP ソルバーよりも高速です。
プログラム全体
プログラム全体を以下に示します。
Python
"""Assignment with teams of workers.""" from ortools.graph.python import min_cost_flow def main(): """Solving an Assignment with teams of worker.""" smcf = min_cost_flow.SimpleMinCostFlow() # Define the directed graph for the flow. team_a = [1, 3, 5] team_b = [2, 4, 6] start_nodes = ( # fmt: off [0, 0] + [11, 11, 11] + [12, 12, 12] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] + [7, 8, 9, 10] # fmt: on ) end_nodes = ( # fmt: off [11, 12] + team_a + team_b + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] + [13, 13, 13, 13] # fmt: on ) capacities = ( # fmt: off [2, 2] + [1, 1, 1] + [1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] # fmt: on ) costs = ( # fmt: off [0, 0] + [0, 0, 0] + [0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95] + [0, 0, 0, 0] # fmt: on ) source = 0 sink = 13 tasks = 4 # Define an array of supplies at each node. supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks] # Add each arc. for i in range(0, len(start_nodes)): smcf.add_arc_with_capacity_and_unit_cost( start_nodes[i], end_nodes[i], capacities[i], costs[i] ) # Add node supplies. for i in range(0, len(supplies)): smcf.set_node_supply(i, supplies[i]) # Find the minimum cost flow between node 0 and node 10. status = smcf.solve() if status == smcf.OPTIMAL: print("Total cost = ", smcf.optimal_cost()) print() for arc in range(smcf.num_arcs()): # Can ignore arcs leading out of source or intermediate, or into sink. if ( smcf.tail(arc) != source and smcf.tail(arc) != 11 and smcf.tail(arc) != 12 and smcf.head(arc) != sink ): # Arcs in the solution will have a flow value of 1. # There start and end nodes give an assignment of worker to task. if smcf.flow(arc) > 0: print( "Worker %d assigned to task %d. Cost = %d" % (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc)) ) else: print("There was an issue with the min cost flow input.") print(f"Status: {status}") if __name__ == "__main__": main()
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h" namespace operations_research { // MinCostFlow simple interface example. void BalanceMinFlow() { // Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow; // Define the directed graph for the flow. const std::vector<int64_t> team_A = {1, 3, 5}; const std::vector<int64_t> team_B = {2, 4, 6}; const std::vector<int64_t> start_nodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; const std::vector<int64_t> end_nodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; const std::vector<int64_t> capacities = {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; const std::vector<int64_t> unit_costs = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; const int64_t source = 0; const int64_t sink = 13; const int64_t tasks = 4; // Define an array of supplies at each node. const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < start_nodes.size(); ++i) { int arc = min_cost_flow.AddArcWithCapacityAndUnitCost( start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]); if (arc != i) LOG(FATAL) << "Internal error"; } // Add node supplies. for (int i = 0; i < supplies.size(); ++i) { min_cost_flow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. int status = min_cost_flow.Solve(); if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into // sink. if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 && min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end // nodes give an assignment of worker to task. if (min_cost_flow.Flow(i) > 0) { LOG(INFO) << "Worker " << min_cost_flow.Tail(i) << " assigned to task " << min_cost_flow.Head(i) << " Cost: " << min_cost_flow.UnitCost(i); } } } } else { LOG(INFO) << "Solving the min cost flow problem failed."; LOG(INFO) << "Solver status: " << status; } } } // namespace operations_research int main() { operations_research::BalanceMinFlow(); return EXIT_SUCCESS; }
Java
package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase; /** Minimal Assignment Min Flow. */ public class BalanceMinFlow { public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define the directed graph for the flow. // int[] teamA = new int[] {1, 3, 5}; // int[] teamB = new int[] {2, 4, 6}; int[] startNodes = new int[] {0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10}; int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13}; int[] capacities = new int[] {2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int[] unitCosts = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0}; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks}; // Add each arc. for (int i = 0; i < startNodes.length; ++i) { int arc = minCostFlow.addArcWithCapacityAndUnitCost( startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) { throw new Exception("Internal error"); } } // Add node supplies. for (int i = 0; i < supplies.length; ++i) { minCostFlow.setNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve(); if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Total cost: " + minCostFlow.getOptimalCost()); System.out.println(); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { // Can ignore arcs leading out of source or intermediate nodes, or into sink. if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11 && minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.getFlow(i) > 0) { System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task " + minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i)); } } } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private BalanceMinFlow() {} }
C#
using System; using Google.OrTools.Graph; public class BalanceMinFlow { static void Main() { // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // Define the directed graph for the flow. int[] teamA = { 1, 3, 5 }; int[] teamB = { 2, 4, 6 }; // Define four parallel arrays: sources, destinations, capacities, and unit costs // between each pair. int[] startNodes = { 0, 0, 11, 11, 11, 12, 12, 12, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 10 }; int[] endNodes = { 11, 12, 1, 3, 5, 2, 4, 6, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 13, 13, 13, 13 }; int[] capacities = { 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; int[] unitCosts = { 0, 0, 0, 0, 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95, 0, 0, 0, 0 }; int source = 0; int sink = 13; int tasks = 4; // Define an array of supplies at each node. int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks }; // Add each arc. for (int i = 0; i < startNodes.Length; ++i) { int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]); if (arc != i) throw new Exception("Internal error"); } // Add node supplies. for (int i = 0; i < supplies.Length; ++i) { minCostFlow.SetNodeSupply(i, supplies[i]); } // Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve(); if (status == MinCostFlow.Status.OPTIMAL) { Console.WriteLine("Total cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { // Can ignore arcs leading out of source or into sink. if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 && minCostFlow.Head(i) != sink) { // Arcs in the solution have a flow value of 1. Their start and end nodes // give an assignment of worker to task. if (minCostFlow.Flow(i) > 0) { Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) + " Cost: " + minCostFlow.UnitCost(i)); } } } } else { Console.WriteLine("Solving the min cost flow problem failed."); Console.WriteLine("Solver status: " + status); } } }