असाइनमेंट की समस्या के खास मामलों को हल करने के लिए, कम से कम लागत वाले फ़्लो सॉल्वर का इस्तेमाल किया जा सकता है.
असल में, कम से कम लागत वाला फ़्लो, अक्सर एमआईपी या सीपी-एसएटी सॉल्वर की तुलना में तेज़ी से समाधान देता है. हालांकि, 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();
डेटा बनाना
समस्या के फ़्लो डायग्राम में, कॉस्ट मैट्रिक्स के लिए दो-पक्षीय ग्राफ़ होता है. एक अलग उदाहरण के लिए, असाइनमेंट की खास जानकारी देखें. इसमें सोर्स और सिंक को जोड़ा गया है.
डेटा में, स्टार्ट नोड, एंड नोड, क्षमता, और समस्या से जुड़ी लागत से जुड़ी ये चार कैटगरी होती हैं. हर ऐरे की लंबाई, ग्राफ़ में मौजूद चाप की संख्या होती है.
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 };
यह बताने के लिए कि डेटा को कैसे सेट अप किया गया है, हर ऐरे को तीन सब-अरे में बांटा जाता है:
- पहली अरे, स्रोत से बाहर जाने वाले चापों के साथ मेल खाती है.
- दूसरी अरे, वर्कर और टास्क के बीच वाले आर्क से मेल खाती है.
costsके लिए, यह सिर्फ़ लागत मैट्रिक्स है (लीनियर असाइनमेंट सॉल्वर का इस्तेमाल करता है), जिसे वेक्टर में फ़्लैट किया जाता है. - तीसरी सरणी, सिंक में ले जाने वाले चापों से संबंधित है.
इस डेटा में वेक्टर supplies भी शामिल है, जो हर नोड पर सप्लाई देता है.
कम से कम लागत के फ़्लो की समस्या, असाइनमेंट में होने वाली समस्या को कैसे दिखाती है
ऊपर दी गई कम से कम लागत फ़्लो की समस्या, असाइनमेंट से जुड़ी समस्या को कैसे दिखाती है? पहला, हर चाप की क्षमता 1 है, इसलिए स्रोत पर 4 की सप्लाई, हर चार चापों को कामगारों तक ले जाने के लिए 1 का प्रवाह बनाती है.
इसके बाद, फ़्लो-इन-फ़्लो-आउट स्थिति में हर वर्कर का फ़्लो 1 हो जाता है. अगर हो सके, तो सॉल्वर हर वर्कर पर कम से कम लागत के फ़्लो को डायरेक्ट करेगा. हालांकि, सॉल्वर डेटा को दो अलग-अलग वर्कर से किसी एक टास्क पर नहीं ले जा सकता. अगर ऐसा हुआ, तो उस टास्क में 2 का संयुक्त फ़्लो होगा, जिसे एक आर्क में नहीं भेजा जा सकता. हालांकि, एक की क्षमता 1 को टास्क से सिंक तक नहीं भेजा जा सकता. इसका मतलब है कि सॉल्वर, असाइनमेंट में पूछे गए सवाल के हिसाब से सिर्फ़ एक वर्कर को टास्क असाइन कर सकता है.
आखिर में, फ़्लो-इन-फ़्लो-आउट स्थिति में हर टास्क को 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.000147 सेकंड बनाम 0.000458 सेकंड.
पूरा कार्यक्रम
पूरा प्रोग्राम नीचे दिखाया गया है.
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);
}
}
}
कर्मचारियों की टीम के साथ असाइनमेंट
यह सेक्शन असाइनमेंट से जुड़ी एक सामान्य समस्या के बारे में बताता है. इस सवाल में, छह कर्मचारियों को दो टीमों में बांटा गया है. इसमें सबसे बड़ी समस्या है कि कर्मचारियों को चार टास्क असाइन किए जाएं, ताकि दोनों टीमों के काम पर बराबर वर्कलोड हो — इसका मतलब है कि हर टीम दो टास्क पूरे करेगी.
इस समस्या को हल करने के लिए, एमआईपी सॉल्वर को Team with Workers के साथ असाइनमेंट करना देखें.
नीचे दिए सेक्शन में एक ऐसे प्रोग्राम के बारे में बताया गया है जो कम से कम लागत वाले फ़्लो सॉल्वर का इस्तेमाल करके, समस्या को हल करता है.
लाइब्रेरी इंपोर्ट करना
नीचे दिया गया कोड, ज़रूरी लाइब्रेरी को इंपोर्ट करता है.
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. नोड 11 को टीम A के नोड से कनेक्ट किया गया है. वहीं नोड 12 को टीम B के नोड से जोड़ा गया है, जिसमें क्षमता 1 के आर्क हैं. नीचे दिया गया ग्राफ़, सोर्स से वर्कर तक के सिर्फ़ नोड और चाप दिखाता है.
वर्कलोड को बैलेंस करने के लिए सबसे ज़रूरी यह है कि सोर्स 0, नोड 11 और 12 को क्षमता 2 के आर्क से जुड़ा हो. इसका मतलब है कि नोड 11 और 12 (यानी टीम A और B) का ज़्यादा से ज़्यादा 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 सेकंड लगते हैं.
पूरा कार्यक्रम
पूरा प्रोग्राम नीचे दिखाया गया है.
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);
}
}
}