最大フローの問題と密接に関連しているのは最小コスト（最小コスト）です。 グラフ上の各円弧に、輸送費用の単価が あります。問題は、合計費用が最も少ないフローを見つけることです。
最小コストフローの問題には、サプライ ノードまたは需要と呼ばれる特別なノードもあります。 これは、Cloud Storage バケットのソースとシンクに マテリアルは供給ノードから需要ノードに輸送されます。
- 供給ノードでは、正の量（供給）が加算されます。 できます。たとえば、そのノードでの生産を供給と表すことができます。
- 需要ノードでは、負の金額（需要）が できます需要はそのノードでの消費を表し、 例です。
便宜上、需要ノードと供給ノード以外のすべてのノードは、 ゼロの供給（および需要）を持つことがわかっています。
最小コストフローの問題には、次のフロー保存ルールがあります。 需要と供給を考慮する
下のグラフは最小コストフローの問題を示しています。円弧はペアでラベル付けされ、 最初の数字は容量、2 番目の数字は費用です。 ノードの横のかっこ内の数字は、供給または需要を表します。ノード ノード 0 はサプライ 20 のサプライノード、ノード 3 と 4 は需要ノードです。 それぞれ -5 と -15 になります。
ライブラリのインポート
次のコードは、必要なライブラリをインポートします。
Python
import numpy as np 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;
解法を宣言する
この問題を解くために、 SimpleMinCostFlow あります。
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 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. start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4]) end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2]) capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5]) unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3]) # Define an array of supplies at each node. supplies = [20, 0, 0, -5, -15]
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. std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4}; std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2}; std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5}; std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. std::vector<int64_t> supplies = {20, 0, 0, -5, -15};
Java
// 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. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4}; int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2}; int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5}; int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. int[] supplies = new int[] {20, 0, 0, -5, -15};
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. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 }; int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 }; int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 }; int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 }; // Define an array of supplies at each node. int[] supplies = { 20, 0, 0, -5, -15 };
円弧を追加する
開始ノードと終了ノードごとに、開始ノードから終了ノードまでの円弧を作成する メソッドを使って、特定の容量と単価で AddArcWithCapacityAndUnitCost。
解法の SetNodeSupply メソッドはノードの物資のベクトルを作成します。
Python
# Add arcs, capacities and costs in bulk using numpy. all_arcs = smcf.add_arcs_with_capacity_and_unit_cost( start_nodes, end_nodes, capacities, unit_costs ) # Add supply for each nodes. smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies)
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]); }
ソルバーを呼び出す
すべての円弧を定義したところで、あとは
結果を表示しますSolve() メソッドを呼び出します。
Python
# Find the min cost flow. 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("There was an issue with the min cost flow input.") print(f"Status: {status}") exit(1) print(f"Minimum cost: {smcf.optimal_cost()}") print("") print(" Arc Flow / Capacity Cost") solution_flows = smcf.flows(all_arcs) costs = solution_flows * unit_costs for arc, flow, cost in zip(all_arcs, solution_flows, costs): print( f"{smcf.tail(arc):1} -> {smcf.head(arc)} {flow:3} / {smcf.capacity(arc):3} {cost}" )
C++
if (status == MinCostFlow::OPTIMAL) { LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity Cost"; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i); LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i) << " " << min_cost_flow.Flow(i) << " / " << min_cost_flow.Capacity(i) << " " << cost; } } else { LOG(INFO) << "Solving the min cost flow problem failed. Solver status: " << status; }
Java
if (status == MinCostFlow.Status.OPTIMAL) { System.out.println("Minimum cost: " + minCostFlow.getOptimalCost()); System.out.println(); System.out.println(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i); System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + " " + minCostFlow.getFlow(i) + " / " + minCostFlow.getCapacity(i) + " " + cost); } } 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("Minimum cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); Console.WriteLine(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i); Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + " " + string.Format("{0,3}", minCostFlow.Flow(i)) + " / " + string.Format("{0,3}", minCostFlow.Capacity(i)) + " " + string.Format("{0,3}", cost)); } } else { Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status); }
Python プログラムの出力は次のとおりです。
Minimum cost: 150 Arc Flow / Capacity Cost 0 -> 1 12 / 15 48 0 -> 2 8 / 8 32 1 -> 2 8 / 20 16 1 -> 3 4 / 4 8 1 -> 4 0 / 10 0 2 -> 3 12 / 15 12 2 -> 4 4 / 4 12 3 -> 4 11 / 20 22 4 -> 2 0 / 5 0
プログラムを完了する
すべてをまとめて、完全なプログラムは次のとおりです。
Python
"""From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1.""" import numpy as np from ortools.graph.python import min_cost_flow def main(): """MinCostFlow simple interface example.""" # Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow() # 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. start_nodes = np.array([0, 0, 1, 1, 1, 2, 2, 3, 4]) end_nodes = np.array([1, 2, 2, 3, 4, 3, 4, 4, 2]) capacities = np.array([15, 8, 20, 4, 10, 15, 4, 20, 5]) unit_costs = np.array([4, 4, 2, 2, 6, 1, 3, 2, 3]) # Define an array of supplies at each node. supplies = [20, 0, 0, -5, -15] # Add arcs, capacities and costs in bulk using numpy. all_arcs = smcf.add_arcs_with_capacity_and_unit_cost( start_nodes, end_nodes, capacities, unit_costs ) # Add supply for each nodes. smcf.set_nodes_supplies(np.arange(0, len(supplies)), supplies) # Find the min cost flow. status = smcf.solve() if status != smcf.OPTIMAL: print("There was an issue with the min cost flow input.") print(f"Status: {status}") exit(1) print(f"Minimum cost: {smcf.optimal_cost()}") print("") print(" Arc Flow / Capacity Cost") solution_flows = smcf.flows(all_arcs) costs = solution_flows * unit_costs for arc, flow, cost in zip(all_arcs, solution_flows, costs): print( f"{smcf.tail(arc):1} -> {smcf.head(arc)} {flow:3} / {smcf.capacity(arc):3} {cost}" ) if __name__ == "__main__": main()
C++
// From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1 #include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h" namespace operations_research { // MinCostFlow simple interface example. void SimpleMinCostFlowProgram() { // 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. std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4}; std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2}; std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5}; std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. std::vector<int64_t> supplies = {20, 0, 0, -5, -15}; // 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) << "Minimum cost flow: " << min_cost_flow.OptimalCost(); LOG(INFO) << ""; LOG(INFO) << " Arc Flow / Capacity Cost"; for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) { int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i); LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i) << " " << min_cost_flow.Flow(i) << " / " << min_cost_flow.Capacity(i) << " " << cost; } } else { LOG(INFO) << "Solving the min cost flow problem failed. Solver status: " << status; } } } // namespace operations_research int main() { operations_research::SimpleMinCostFlowProgram(); return EXIT_SUCCESS; }
Java
// From Bradley, Hax, and Maganti, 'Applied Mathematical Programming', figure 8.1. package com.google.ortools.graph.samples; import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase; /** Minimal MinCostFlow program. */ public class SimpleMinCostFlowProgram { 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. For instance, the arc from node 0 to node 1 has a // capacity of 15. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4}; int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2}; int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5}; int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3}; // Define an array of supplies at each node. int[] supplies = new int[] {20, 0, 0, -5, -15}; // 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("Minimum cost: " + minCostFlow.getOptimalCost()); System.out.println(); System.out.println(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.getNumArcs(); ++i) { long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i); System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + " " + minCostFlow.getFlow(i) + " / " + minCostFlow.getCapacity(i) + " " + cost); } } else { System.out.println("Solving the min cost flow problem failed."); System.out.println("Solver status: " + status); } } private SimpleMinCostFlowProgram() {} }
C#
// From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1. using System; using Google.OrTools.Graph; public class SimpleMinCostFlowProgram { static void Main() { // Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow(); // 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. // Problem taken From Taha's 'Introduction to Operations Research', // example 6.4-2. int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 }; int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 }; int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 }; int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 }; // Define an array of supplies at each node. int[] supplies = { 20, 0, 0, -5, -15 }; // 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("Minimum cost: " + minCostFlow.OptimalCost()); Console.WriteLine(""); Console.WriteLine(" Edge Flow / Capacity Cost"); for (int i = 0; i < minCostFlow.NumArcs(); ++i) { long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i); Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + " " + string.Format("{0,3}", minCostFlow.Flow(i)) + " / " + string.Format("{0,3}", minCostFlow.Capacity(i)) + " " + string.Format("{0,3}", cost)); } } else { Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status); } } }