Cette section décrit un problème d'attribution dans lequel seuls certains groupes de nœuds de calcul autorisés peuvent être affectés aux tâches. Dans l'exemple, il y a douze nœuds de calcul, numérotés de 0 à 11. Les groupes autorisés sont des combinaisons des paires de nœuds de calcul suivantes.
group1 = [[2, 3], # Subgroups of workers 0 - 3 [1, 3], [1, 2], [0, 1], [0, 2]]group2 = [[6, 7], # Subgroups of workers 4 - 7 [5, 7], [5, 6], [4, 5], [4, 7]]
group3 = [[10, 11], # Subgroups of workers 8 - 11 [9, 11], [9, 10], [8, 10], [8, 11]]
Un groupe autorisé peut être une combinaison de trois paires de nœuds de calcul, une paire provenant de chacun des groupes group1, group2 et group3.
Par exemple, la combinaison de [2, 3]
, [6, 7]
et [10, 11]
génère le groupe autorisé [2, 3, 6, 7, 10, 11]
.
Étant donné que chacun des trois ensembles contient cinq éléments, le nombre total de groupes autorisés est de 5 * 5 * 5 = 125
.
Notez qu'un groupe de nœuds de calcul peut être une solution au problème s'il appartient à l'un des groupes autorisés. En d'autres termes, l'ensemble réalisable est constitué de points pour lesquels l'une des contraintes est satisfaite. Voici un exemple de problème non convexe. En revanche, l'exemple MIP, décrit précédemment, est un problème convexe: pour qu'un point soit réalisable, toutes les contraintes doivent être satisfaites.
Pour des problèmes non convexes comme celui-ci, le résolveur CP-SAT est généralement plus rapide qu'un résolveur MIP. Les sections suivantes présentent des solutions au problème à l'aide du résolveur CP-SAT et du résolveur MIP, et comparent les temps de solution des deux solutions.
Solution CP-SAT
Tout d'abord, nous allons décrire une solution au problème à l'aide de l'outil CP-SAT.
Importer les bibliothèques
Le code suivant importe la bibliothèque requise.
Python
from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <cstdint> #include <numeric> #include <vector> #include "absl/strings/str_format.h" #include "absl/types/span.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.IntVar; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat;
Définir les données
Le code suivant crée les données pour le programme.
Python
costs = [ [90, 76, 75, 70, 50, 74], [35, 85, 55, 65, 48, 101], [125, 95, 90, 105, 59, 120], [45, 110, 95, 115, 104, 83], [60, 105, 80, 75, 59, 62], [45, 65, 110, 95, 47, 31], [38, 51, 107, 41, 69, 99], [47, 85, 57, 71, 92, 77], [39, 63, 97, 49, 118, 56], [47, 101, 71, 60, 88, 109], [17, 39, 103, 64, 61, 92], [101, 45, 83, 59, 92, 27], ] num_workers = len(costs) num_tasks = len(costs[0])
C++
const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70, 50, 74}}, {{35, 85, 55, 65, 48, 101}}, {{125, 95, 90, 105, 59, 120}}, {{45, 110, 95, 115, 104, 83}}, {{60, 105, 80, 75, 59, 62}}, {{45, 65, 110, 95, 47, 31}}, {{38, 51, 107, 41, 69, 99}}, {{47, 85, 57, 71, 92, 77}}, {{39, 63, 97, 49, 118, 56}}, {{47, 101, 71, 60, 88, 109}}, {{17, 39, 103, 64, 61, 92}}, {{101, 45, 83, 59, 92, 27}}, }}; const int num_workers = static_cast<int>(costs.size()); std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = static_cast<int>(costs[0].size()); std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0);
Java
int[][] costs = { {90, 76, 75, 70, 50, 74}, {35, 85, 55, 65, 48, 101}, {125, 95, 90, 105, 59, 120}, {45, 110, 95, 115, 104, 83}, {60, 105, 80, 75, 59, 62}, {45, 65, 110, 95, 47, 31}, {38, 51, 107, 41, 69, 99}, {47, 85, 57, 71, 92, 77}, {39, 63, 97, 49, 118, 56}, {47, 101, 71, 60, 88, 109}, {17, 39, 103, 64, 61, 92}, {101, 45, 83, 59, 92, 27}, }; final int numWorkers = costs.length; final int numTasks = costs[0].length; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray();
C#
int[,] costs = { { 90, 76, 75, 70, 50, 74 }, { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 }, { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 }, { 38, 51, 107, 41, 69, 99 }, { 47, 85, 57, 71, 92, 77 }, { 39, 63, 97, 49, 118, 56 }, { 47, 101, 71, 60, 88, 109 }, { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
Créer les groupes autorisés
Pour définir les groupes de nœuds de calcul autorisés pour le résolveur CP-SAT, vous devez créer des tableaux binaires indiquant quels nœuds de calcul appartiennent à un groupe. Par exemple, pour group1
(nœuds de calcul 0 - 3), le vecteur binaire [0, 0, 1, 1]
spécifie le groupe contenant les nœuds de calcul 2 et 3.
Les tableaux suivants définissent les groupes de nœuds de calcul autorisés.
Python
group1 = [ [0, 0, 1, 1], # Workers 2, 3 [0, 1, 0, 1], # Workers 1, 3 [0, 1, 1, 0], # Workers 1, 2 [1, 1, 0, 0], # Workers 0, 1 [1, 0, 1, 0], # Workers 0, 2 ] group2 = [ [0, 0, 1, 1], # Workers 6, 7 [0, 1, 0, 1], # Workers 5, 7 [0, 1, 1, 0], # Workers 5, 6 [1, 1, 0, 0], # Workers 4, 5 [1, 0, 0, 1], # Workers 4, 7 ] group3 = [ [0, 0, 1, 1], # Workers 10, 11 [0, 1, 0, 1], # Workers 9, 11 [0, 1, 1, 0], # Workers 9, 10 [1, 0, 1, 0], # Workers 8, 10 [1, 0, 0, 1], # Workers 8, 11 ]
C++
const std::vector<std::vector<int64_t>> group1 = {{ {{0, 0, 1, 1}}, // Workers 2, 3 {{0, 1, 0, 1}}, // Workers 1, 3 {{0, 1, 1, 0}}, // Workers 1, 2 {{1, 1, 0, 0}}, // Workers 0, 1 {{1, 0, 1, 0}}, // Workers 0, 2 }}; const std::vector<std::vector<int64_t>> group2 = {{ {{0, 0, 1, 1}}, // Workers 6, 7 {{0, 1, 0, 1}}, // Workers 5, 7 {{0, 1, 1, 0}}, // Workers 5, 6 {{1, 1, 0, 0}}, // Workers 4, 5 {{1, 0, 0, 1}}, // Workers 4, 7 }}; const std::vector<std::vector<int64_t>> group3 = {{ {{0, 0, 1, 1}}, // Workers 10, 11 {{0, 1, 0, 1}}, // Workers 9, 11 {{0, 1, 1, 0}}, // Workers 9, 10 {{1, 0, 1, 0}}, // Workers 8, 10 {{1, 0, 0, 1}}, // Workers 8, 11 }};
Java
int[][] group1 = { {0, 0, 1, 1}, // Workers 2, 3 {0, 1, 0, 1}, // Workers 1, 3 {0, 1, 1, 0}, // Workers 1, 2 {1, 1, 0, 0}, // Workers 0, 1 {1, 0, 1, 0}, // Workers 0, 2 }; int[][] group2 = { {0, 0, 1, 1}, // Workers 6, 7 {0, 1, 0, 1}, // Workers 5, 7 {0, 1, 1, 0}, // Workers 5, 6 {1, 1, 0, 0}, // Workers 4, 5 {1, 0, 0, 1}, // Workers 4, 7 }; int[][] group3 = { {0, 0, 1, 1}, // Workers 10, 11 {0, 1, 0, 1}, // Workers 9, 11 {0, 1, 1, 0}, // Workers 9, 10 {1, 0, 1, 0}, // Workers 8, 10 {1, 0, 0, 1}, // Workers 8, 11 };
C#
long[,] group1 = { { 0, 0, 1, 1 }, // Workers 2, 3 { 0, 1, 0, 1 }, // Workers 1, 3 { 0, 1, 1, 0 }, // Workers 1, 2 { 1, 1, 0, 0 }, // Workers 0, 1 { 1, 0, 1, 0 }, // Workers 0, 2 }; long[,] group2 = { { 0, 0, 1, 1 }, // Workers 6, 7 { 0, 1, 0, 1 }, // Workers 5, 7 { 0, 1, 1, 0 }, // Workers 5, 6 { 1, 1, 0, 0 }, // Workers 4, 5 { 1, 0, 0, 1 }, // Workers 4, 7 }; long[,] group3 = { { 0, 0, 1, 1 }, // Workers 10, 11 { 0, 1, 0, 1 }, // Workers 9, 11 { 0, 1, 1, 0 }, // Workers 9, 10 { 1, 0, 1, 0 }, // Workers 8, 10 { 1, 0, 0, 1 }, // Workers 8, 11 };
Pour CP-SAT, il n'est pas nécessaire de créer les 125 combinaisons de ces vecteurs dans une boucle. Le résolveur CP-SAT fournit une méthode, AllowedAssignments
, qui vous permet de spécifier séparément les contraintes des groupes autorisés pour chacun des trois ensembles de nœuds de calcul (0 à 3, 4 à 7 et 8 à 11).
Comment ça marche ?
Python
# Create variables for each worker, indicating whether they work on some task. work = {} for worker in range(num_workers): work[worker] = model.new_bool_var(f"work[{worker}]") for worker in range(num_workers): for task in range(num_tasks): model.add(work[worker] == sum(x[worker, task] for task in range(num_tasks))) # Define the allowed groups of worders model.add_allowed_assignments([work[0], work[1], work[2], work[3]], group1) model.add_allowed_assignments([work[4], work[5], work[6], work[7]], group2) model.add_allowed_assignments([work[8], work[9], work[10], work[11]], group3)
C++
// Create variables for each worker, indicating whether they work on some // task. std::vector<IntVar> work(num_workers); for (int worker : all_workers) { work[worker] = IntVar( cp_model.NewBoolVar().WithName(absl::StrFormat("work[%d]", worker))); } for (int worker : all_workers) { LinearExpr task_sum; for (int task : all_tasks) { task_sum += x[worker][task]; } cp_model.AddEquality(work[worker], task_sum); } // Define the allowed groups of worders auto table1 = cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]}); for (const auto& t : group1) { table1.AddTuple(t); } auto table2 = cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]}); for (const auto& t : group2) { table2.AddTuple(t); } auto table3 = cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]}); for (const auto& t : group3) { table3.AddTuple(t); }
Java
// Create variables for each worker, indicating whether they work on some task. IntVar[] work = new IntVar[numWorkers]; for (int worker : allWorkers) { work[worker] = model.newBoolVar("work[" + worker + "]"); } for (int worker : allWorkers) { LinearExprBuilder expr = LinearExpr.newBuilder(); for (int task : allTasks) { expr.add(x[worker][task]); } model.addEquality(work[worker], expr); } // Define the allowed groups of worders model.addAllowedAssignments(new IntVar[] {work[0], work[1], work[2], work[3]}) .addTuples(group1); model.addAllowedAssignments(new IntVar[] {work[4], work[5], work[6], work[7]}) .addTuples(group2); model.addAllowedAssignments(new IntVar[] {work[8], work[9], work[10], work[11]}) .addTuples(group3);
C#
// Create variables for each worker, indicating whether they work on some task. BoolVar[] work = new BoolVar[numWorkers]; foreach (int worker in allWorkers) { work[worker] = model.NewBoolVar($"work[{worker}]"); } foreach (int worker in allWorkers) { List<ILiteral> tasks = new List<ILiteral>(); foreach (int task in allTasks) { tasks.Add(x[worker, task]); } model.Add(work[worker] == LinearExpr.Sum(tasks)); } // Define the allowed groups of worders model.AddAllowedAssignments(new IntVar[] { work[0], work[1], work[2], work[3] }).AddTuples(group1); model.AddAllowedAssignments(new IntVar[] { work[4], work[5], work[6], work[7] }).AddTuples(group2); model.AddAllowedAssignments(new IntVar[] { work[8], work[9], work[10], work[11] }).AddTuples(group3);
Les variables work[i]
sont des variables comprises entre 0 et 1 qui indiquent l'état du travail ou chaque nœud de calcul. Autrement dit, work[i]
est égal à 1 si le nœud de calcul i est attribué à une tâche, et à 0 dans le cas contraire. La ligne solver.Add(solver.AllowedAssignments([work[0], work[1], work[2], work[3]], group1))
définit la contrainte selon laquelle l'état de travail des nœuds de calcul 0 à 3 doit correspondre à l'un des modèles de group1
. Vous trouverez des informations complètes sur le code dans la section suivante.
Créer le modèle
Le code suivant crée le modèle.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Créer les variables
Le code suivant crée un tableau de variables pour le problème.
Python
x = {} for worker in range(num_workers): for task in range(num_tasks): x[worker, task] = model.new_bool_var(f"x[{worker},{task}]")
C++
// x[i][j] is an array of Boolean variables. x[i][j] is true // if worker i is assigned to task j. std::vector<std::vector<BoolVar>> x(num_workers, std::vector<BoolVar>(num_tasks)); for (int worker : all_workers) { for (int task : all_tasks) { x[worker][task] = cp_model.NewBoolVar().WithName( absl::StrFormat("x[%d,%d]", worker, task)); } }
Java
Literal[][] x = new Literal[numWorkers][numTasks]; for (int worker : allWorkers) { for (int task : allTasks) { x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]"); } }
C#
BoolVar[,] x = new BoolVar[numWorkers, numTasks]; // Variables in a 1-dim array. foreach (int worker in allWorkers) { foreach (int task in allTasks) { x[worker, task] = model.NewBoolVar($"x[{worker},{task}]"); } }
Ajouter les contraintes
Le code suivant crée les contraintes du programme.
Python
# Each worker is assigned to at most one task. for worker in range(num_workers): model.add_at_most_one(x[worker, task] for task in range(num_tasks)) # Each task is assigned to exactly one worker. for task in range(num_tasks): model.add_exactly_one(x[worker, task] for worker in range(num_workers))
C++
// Each worker is assigned to at most one task. for (int worker : all_workers) { cp_model.AddAtMostOne(x[worker]); } // Each task is assigned to exactly one worker. for (int task : all_tasks) { std::vector<BoolVar> tasks; for (int worker : all_workers) { tasks.push_back(x[worker][task]); } cp_model.AddExactlyOne(tasks); }
Java
// Each worker is assigned to at most one task. for (int worker : allWorkers) { List<Literal> tasks = new ArrayList<>(); for (int task : allTasks) { tasks.add(x[worker][task]); } model.addAtMostOne(tasks); } // Each task is assigned to exactly one worker. for (int task : allTasks) { List<Literal> workers = new ArrayList<>(); for (int worker : allWorkers) { workers.add(x[worker][task]); } model.addExactlyOne(workers); }
C#
// Each worker is assigned to at most one task. foreach (int worker in allWorkers) { List<ILiteral> tasks = new List<ILiteral>(); foreach (int task in allTasks) { tasks.Add(x[worker, task]); } model.AddAtMostOne(tasks); } // Each task is assigned to exactly one worker. foreach (int task in allTasks) { List<ILiteral> workers = new List<ILiteral>(); foreach (int worker in allWorkers) { workers.Add(x[worker, task]); } model.AddExactlyOne(workers); }
Créer l'objectif
Le code suivant crée la fonction objectif.
Python
objective_terms = [] for worker in range(num_workers): for task in range(num_tasks): objective_terms.append(costs[worker][task] * x[worker, task]) model.minimize(sum(objective_terms))
C++
LinearExpr total_cost; for (int worker : all_workers) { for (int task : all_tasks) { total_cost += x[worker][task] * costs[worker][task]; } } cp_model.Minimize(total_cost);
Java
LinearExprBuilder obj = LinearExpr.newBuilder(); for (int worker : allWorkers) { for (int task : allTasks) { obj.addTerm(x[worker][task], costs[worker][task]); } } model.minimize(obj);
C#
LinearExprBuilder obj = LinearExpr.NewBuilder(); foreach (int worker in allWorkers) { foreach (int task in allTasks) { obj.AddTerm(x[worker, task], costs[worker, task]); } } model.Minimize(obj);
Appeler le résolveur
Le code suivant appelle le résolveur et affiche les résultats.
Python
solver = cp_model.CpSolver() status = solver.solve(model)
C++
const CpSolverResponse response = Solve(cp_model.Build());
Java
CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model);
C#
CpSolver solver = new CpSolver(); CpSolverStatus status = solver.Solve(model); Console.WriteLine($"Solve status: {status}");
Afficher les résultats
Nous pouvons maintenant imprimer la solution.
Python
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print(f"Total cost = {solver.objective_value}\n") for worker in range(num_workers): for task in range(num_tasks): if solver.boolean_value(x[worker, task]): print( f"Worker {worker} assigned to task {task}." + f" Cost = {costs[worker][task]}" ) else: print("No solution found.")
C++
if (response.status() == CpSolverStatus::INFEASIBLE) { LOG(FATAL) << "No solution found."; } LOG(INFO) << "Total cost: " << response.objective_value(); LOG(INFO); for (int worker : all_workers) { for (int task : all_tasks) { if (SolutionBooleanValue(response, x[worker][task])) { LOG(INFO) << "Worker " << worker << " assigned to task " << task << ". Cost: " << costs[worker][task]; } } }
Java
// Check that the problem has a feasible solution. if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { System.out.println("Total cost: " + solver.objectiveValue() + "\n"); for (int worker : allWorkers) { for (int task : allTasks) { if (solver.booleanValue(x[worker][task])) { System.out.println("Worker " + worker + " assigned to task " + task + ". Cost: " + costs[worker][task]); } } } } else { System.err.println("No solution found."); }
C#
// Check that the problem has a feasible solution. if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n"); foreach (int worker in allWorkers) { foreach (int task in allTasks) { if (solver.Value(x[worker, task]) > 0.5) { Console.WriteLine($"Worker {worker} assigned to task {task}. " + $"Cost: {costs[worker, task]}"); } } } } else { Console.WriteLine("No solution found."); }
Voici la sortie du programme.
Minimum cost = 239 Worker 0 assigned to task 4 Cost = 50 Worker 1 assigned to task 2 Cost = 55 Worker 5 assigned to task 5 Cost = 31 Worker 6 assigned to task 3 Cost = 41 Worker 10 assigned to task 0 Cost = 17 Worker 11 assigned to task 1 Cost = 45 Time = 0.0113 seconds
L'ensemble du programme
Voici le programme complet.
Python
"""Solves an assignment problem for given group of workers.""" from ortools.sat.python import cp_model def main() -> None: # Data costs = [ [90, 76, 75, 70, 50, 74], [35, 85, 55, 65, 48, 101], [125, 95, 90, 105, 59, 120], [45, 110, 95, 115, 104, 83], [60, 105, 80, 75, 59, 62], [45, 65, 110, 95, 47, 31], [38, 51, 107, 41, 69, 99], [47, 85, 57, 71, 92, 77], [39, 63, 97, 49, 118, 56], [47, 101, 71, 60, 88, 109], [17, 39, 103, 64, 61, 92], [101, 45, 83, 59, 92, 27], ] num_workers = len(costs) num_tasks = len(costs[0]) # Allowed groups of workers: group1 = [ [0, 0, 1, 1], # Workers 2, 3 [0, 1, 0, 1], # Workers 1, 3 [0, 1, 1, 0], # Workers 1, 2 [1, 1, 0, 0], # Workers 0, 1 [1, 0, 1, 0], # Workers 0, 2 ] group2 = [ [0, 0, 1, 1], # Workers 6, 7 [0, 1, 0, 1], # Workers 5, 7 [0, 1, 1, 0], # Workers 5, 6 [1, 1, 0, 0], # Workers 4, 5 [1, 0, 0, 1], # Workers 4, 7 ] group3 = [ [0, 0, 1, 1], # Workers 10, 11 [0, 1, 0, 1], # Workers 9, 11 [0, 1, 1, 0], # Workers 9, 10 [1, 0, 1, 0], # Workers 8, 10 [1, 0, 0, 1], # Workers 8, 11 ] # Model model = cp_model.CpModel() # Variables x = {} for worker in range(num_workers): for task in range(num_tasks): x[worker, task] = model.new_bool_var(f"x[{worker},{task}]") # Constraints # Each worker is assigned to at most one task. for worker in range(num_workers): model.add_at_most_one(x[worker, task] for task in range(num_tasks)) # Each task is assigned to exactly one worker. for task in range(num_tasks): model.add_exactly_one(x[worker, task] for worker in range(num_workers)) # Create variables for each worker, indicating whether they work on some task. work = {} for worker in range(num_workers): work[worker] = model.new_bool_var(f"work[{worker}]") for worker in range(num_workers): for task in range(num_tasks): model.add(work[worker] == sum(x[worker, task] for task in range(num_tasks))) # Define the allowed groups of worders model.add_allowed_assignments([work[0], work[1], work[2], work[3]], group1) model.add_allowed_assignments([work[4], work[5], work[6], work[7]], group2) model.add_allowed_assignments([work[8], work[9], work[10], work[11]], group3) # Objective objective_terms = [] for worker in range(num_workers): for task in range(num_tasks): objective_terms.append(costs[worker][task] * x[worker, task]) model.minimize(sum(objective_terms)) # Solve solver = cp_model.CpSolver() status = solver.solve(model) # Print solution. if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print(f"Total cost = {solver.objective_value}\n") for worker in range(num_workers): for task in range(num_tasks): if solver.boolean_value(x[worker, task]): print( f"Worker {worker} assigned to task {task}." + f" Cost = {costs[worker][task]}" ) else: print("No solution found.") if __name__ == "__main__": main()
C++
// Solve assignment problem for given group of workers. #include <stdlib.h> #include <cstdint> #include <numeric> #include <vector> #include "absl/strings/str_format.h" #include "absl/types/span.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" namespace operations_research { namespace sat { void AssignmentGroups() { // Data const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70, 50, 74}}, {{35, 85, 55, 65, 48, 101}}, {{125, 95, 90, 105, 59, 120}}, {{45, 110, 95, 115, 104, 83}}, {{60, 105, 80, 75, 59, 62}}, {{45, 65, 110, 95, 47, 31}}, {{38, 51, 107, 41, 69, 99}}, {{47, 85, 57, 71, 92, 77}}, {{39, 63, 97, 49, 118, 56}}, {{47, 101, 71, 60, 88, 109}}, {{17, 39, 103, 64, 61, 92}}, {{101, 45, 83, 59, 92, 27}}, }}; const int num_workers = static_cast<int>(costs.size()); std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = static_cast<int>(costs[0].size()); std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0); // Allowed groups of workers: const std::vector<std::vector<int64_t>> group1 = {{ {{0, 0, 1, 1}}, // Workers 2, 3 {{0, 1, 0, 1}}, // Workers 1, 3 {{0, 1, 1, 0}}, // Workers 1, 2 {{1, 1, 0, 0}}, // Workers 0, 1 {{1, 0, 1, 0}}, // Workers 0, 2 }}; const std::vector<std::vector<int64_t>> group2 = {{ {{0, 0, 1, 1}}, // Workers 6, 7 {{0, 1, 0, 1}}, // Workers 5, 7 {{0, 1, 1, 0}}, // Workers 5, 6 {{1, 1, 0, 0}}, // Workers 4, 5 {{1, 0, 0, 1}}, // Workers 4, 7 }}; const std::vector<std::vector<int64_t>> group3 = {{ {{0, 0, 1, 1}}, // Workers 10, 11 {{0, 1, 0, 1}}, // Workers 9, 11 {{0, 1, 1, 0}}, // Workers 9, 10 {{1, 0, 1, 0}}, // Workers 8, 10 {{1, 0, 0, 1}}, // Workers 8, 11 }}; // Model CpModelBuilder cp_model; // Variables // x[i][j] is an array of Boolean variables. x[i][j] is true // if worker i is assigned to task j. std::vector<std::vector<BoolVar>> x(num_workers, std::vector<BoolVar>(num_tasks)); for (int worker : all_workers) { for (int task : all_tasks) { x[worker][task] = cp_model.NewBoolVar().WithName( absl::StrFormat("x[%d,%d]", worker, task)); } } // Constraints // Each worker is assigned to at most one task. for (int worker : all_workers) { cp_model.AddAtMostOne(x[worker]); } // Each task is assigned to exactly one worker. for (int task : all_tasks) { std::vector<BoolVar> tasks; for (int worker : all_workers) { tasks.push_back(x[worker][task]); } cp_model.AddExactlyOne(tasks); } // Create variables for each worker, indicating whether they work on some // task. std::vector<IntVar> work(num_workers); for (int worker : all_workers) { work[worker] = IntVar( cp_model.NewBoolVar().WithName(absl::StrFormat("work[%d]", worker))); } for (int worker : all_workers) { LinearExpr task_sum; for (int task : all_tasks) { task_sum += x[worker][task]; } cp_model.AddEquality(work[worker], task_sum); } // Define the allowed groups of worders auto table1 = cp_model.AddAllowedAssignments({work[0], work[1], work[2], work[3]}); for (const auto& t : group1) { table1.AddTuple(t); } auto table2 = cp_model.AddAllowedAssignments({work[4], work[5], work[6], work[7]}); for (const auto& t : group2) { table2.AddTuple(t); } auto table3 = cp_model.AddAllowedAssignments({work[8], work[9], work[10], work[11]}); for (const auto& t : group3) { table3.AddTuple(t); } // Objective LinearExpr total_cost; for (int worker : all_workers) { for (int task : all_tasks) { total_cost += x[worker][task] * costs[worker][task]; } } cp_model.Minimize(total_cost); // Solve const CpSolverResponse response = Solve(cp_model.Build()); // Print solution. if (response.status() == CpSolverStatus::INFEASIBLE) { LOG(FATAL) << "No solution found."; } LOG(INFO) << "Total cost: " << response.objective_value(); LOG(INFO); for (int worker : all_workers) { for (int task : all_tasks) { if (SolutionBooleanValue(response, x[worker][task])) { LOG(INFO) << "Worker " << worker << " assigned to task " << task << ". Cost: " << costs[worker][task]; } } } } } // namespace sat } // namespace operations_research int main(int argc, char** argv) { operations_research::sat::AssignmentGroups(); return EXIT_SUCCESS; }
Java
// CP-SAT example that solves an assignment problem. package com.google.ortools.sat.samples; import com.google.ortools.Loader; import com.google.ortools.sat.CpModel; import com.google.ortools.sat.CpSolver; import com.google.ortools.sat.CpSolverStatus; import com.google.ortools.sat.IntVar; import com.google.ortools.sat.LinearExpr; import com.google.ortools.sat.LinearExprBuilder; import com.google.ortools.sat.Literal; import java.util.ArrayList; import java.util.List; import java.util.stream.IntStream; /** Assignment problem. */ public class AssignmentGroupsSat { public static void main(String[] args) { Loader.loadNativeLibraries(); // Data int[][] costs = { {90, 76, 75, 70, 50, 74}, {35, 85, 55, 65, 48, 101}, {125, 95, 90, 105, 59, 120}, {45, 110, 95, 115, 104, 83}, {60, 105, 80, 75, 59, 62}, {45, 65, 110, 95, 47, 31}, {38, 51, 107, 41, 69, 99}, {47, 85, 57, 71, 92, 77}, {39, 63, 97, 49, 118, 56}, {47, 101, 71, 60, 88, 109}, {17, 39, 103, 64, 61, 92}, {101, 45, 83, 59, 92, 27}, }; final int numWorkers = costs.length; final int numTasks = costs[0].length; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray(); // Allowed groups of workers: int[][] group1 = { {0, 0, 1, 1}, // Workers 2, 3 {0, 1, 0, 1}, // Workers 1, 3 {0, 1, 1, 0}, // Workers 1, 2 {1, 1, 0, 0}, // Workers 0, 1 {1, 0, 1, 0}, // Workers 0, 2 }; int[][] group2 = { {0, 0, 1, 1}, // Workers 6, 7 {0, 1, 0, 1}, // Workers 5, 7 {0, 1, 1, 0}, // Workers 5, 6 {1, 1, 0, 0}, // Workers 4, 5 {1, 0, 0, 1}, // Workers 4, 7 }; int[][] group3 = { {0, 0, 1, 1}, // Workers 10, 11 {0, 1, 0, 1}, // Workers 9, 11 {0, 1, 1, 0}, // Workers 9, 10 {1, 0, 1, 0}, // Workers 8, 10 {1, 0, 0, 1}, // Workers 8, 11 }; // Model CpModel model = new CpModel(); // Variables Literal[][] x = new Literal[numWorkers][numTasks]; for (int worker : allWorkers) { for (int task : allTasks) { x[worker][task] = model.newBoolVar("x[" + worker + "," + task + "]"); } } // Constraints // Each worker is assigned to at most one task. for (int worker : allWorkers) { List<Literal> tasks = new ArrayList<>(); for (int task : allTasks) { tasks.add(x[worker][task]); } model.addAtMostOne(tasks); } // Each task is assigned to exactly one worker. for (int task : allTasks) { List<Literal> workers = new ArrayList<>(); for (int worker : allWorkers) { workers.add(x[worker][task]); } model.addExactlyOne(workers); } // Create variables for each worker, indicating whether they work on some task. IntVar[] work = new IntVar[numWorkers]; for (int worker : allWorkers) { work[worker] = model.newBoolVar("work[" + worker + "]"); } for (int worker : allWorkers) { LinearExprBuilder expr = LinearExpr.newBuilder(); for (int task : allTasks) { expr.add(x[worker][task]); } model.addEquality(work[worker], expr); } // Define the allowed groups of worders model.addAllowedAssignments(new IntVar[] {work[0], work[1], work[2], work[3]}) .addTuples(group1); model.addAllowedAssignments(new IntVar[] {work[4], work[5], work[6], work[7]}) .addTuples(group2); model.addAllowedAssignments(new IntVar[] {work[8], work[9], work[10], work[11]}) .addTuples(group3); // Objective LinearExprBuilder obj = LinearExpr.newBuilder(); for (int worker : allWorkers) { for (int task : allTasks) { obj.addTerm(x[worker][task], costs[worker][task]); } } model.minimize(obj); // Solve CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model); // Print solution. // Check that the problem has a feasible solution. if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { System.out.println("Total cost: " + solver.objectiveValue() + "\n"); for (int worker : allWorkers) { for (int task : allTasks) { if (solver.booleanValue(x[worker][task])) { System.out.println("Worker " + worker + " assigned to task " + task + ". Cost: " + costs[worker][task]); } } } } else { System.err.println("No solution found."); } } private AssignmentGroupsSat() {} }
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat; public class AssignmentGroupsSat { public static void Main(String[] args) { // Data. int[,] costs = { { 90, 76, 75, 70, 50, 74 }, { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 }, { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 }, { 38, 51, 107, 41, 69, 99 }, { 47, 85, 57, 71, 92, 77 }, { 39, 63, 97, 49, 118, 56 }, { 47, 101, 71, 60, 88, 109 }, { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); // Allowed groups of workers: long[,] group1 = { { 0, 0, 1, 1 }, // Workers 2, 3 { 0, 1, 0, 1 }, // Workers 1, 3 { 0, 1, 1, 0 }, // Workers 1, 2 { 1, 1, 0, 0 }, // Workers 0, 1 { 1, 0, 1, 0 }, // Workers 0, 2 }; long[,] group2 = { { 0, 0, 1, 1 }, // Workers 6, 7 { 0, 1, 0, 1 }, // Workers 5, 7 { 0, 1, 1, 0 }, // Workers 5, 6 { 1, 1, 0, 0 }, // Workers 4, 5 { 1, 0, 0, 1 }, // Workers 4, 7 }; long[,] group3 = { { 0, 0, 1, 1 }, // Workers 10, 11 { 0, 1, 0, 1 }, // Workers 9, 11 { 0, 1, 1, 0 }, // Workers 9, 10 { 1, 0, 1, 0 }, // Workers 8, 10 { 1, 0, 0, 1 }, // Workers 8, 11 }; // Model. CpModel model = new CpModel(); // Variables. BoolVar[,] x = new BoolVar[numWorkers, numTasks]; // Variables in a 1-dim array. foreach (int worker in allWorkers) { foreach (int task in allTasks) { x[worker, task] = model.NewBoolVar($"x[{worker},{task}]"); } } // Constraints // Each worker is assigned to at most one task. foreach (int worker in allWorkers) { List<ILiteral> tasks = new List<ILiteral>(); foreach (int task in allTasks) { tasks.Add(x[worker, task]); } model.AddAtMostOne(tasks); } // Each task is assigned to exactly one worker. foreach (int task in allTasks) { List<ILiteral> workers = new List<ILiteral>(); foreach (int worker in allWorkers) { workers.Add(x[worker, task]); } model.AddExactlyOne(workers); } // Create variables for each worker, indicating whether they work on some task. BoolVar[] work = new BoolVar[numWorkers]; foreach (int worker in allWorkers) { work[worker] = model.NewBoolVar($"work[{worker}]"); } foreach (int worker in allWorkers) { List<ILiteral> tasks = new List<ILiteral>(); foreach (int task in allTasks) { tasks.Add(x[worker, task]); } model.Add(work[worker] == LinearExpr.Sum(tasks)); } // Define the allowed groups of worders model.AddAllowedAssignments(new IntVar[] { work[0], work[1], work[2], work[3] }).AddTuples(group1); model.AddAllowedAssignments(new IntVar[] { work[4], work[5], work[6], work[7] }).AddTuples(group2); model.AddAllowedAssignments(new IntVar[] { work[8], work[9], work[10], work[11] }).AddTuples(group3); // Objective LinearExprBuilder obj = LinearExpr.NewBuilder(); foreach (int worker in allWorkers) { foreach (int task in allTasks) { obj.AddTerm(x[worker, task], costs[worker, task]); } } model.Minimize(obj); // Solve CpSolver solver = new CpSolver(); CpSolverStatus status = solver.Solve(model); Console.WriteLine($"Solve status: {status}"); // Print solution. // Check that the problem has a feasible solution. if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine($"Total cost: {solver.ObjectiveValue}\n"); foreach (int worker in allWorkers) { foreach (int task in allTasks) { if (solver.Value(x[worker, task]) > 0.5) { Console.WriteLine($"Worker {worker} assigned to task {task}. " + $"Cost: {costs[worker, task]}"); } } } } else { Console.WriteLine("No solution found."); } Console.WriteLine("Statistics"); Console.WriteLine($" - conflicts : {solver.NumConflicts()}"); Console.WriteLine($" - branches : {solver.NumBranches()}"); Console.WriteLine($" - wall time : {solver.WallTime()}s"); } }
Solution MIP
Nous décrivons ensuite une solution au problème à l'aide du résolveur MIP.
Importer les bibliothèques
Le code suivant importe la bibliothèque requise.
Python
from ortools.linear_solver import pywraplp
C++
#include <cstdint> #include <memory> #include <numeric> #include <utility> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/linear_solver/linear_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable; import java.util.stream.IntStream;
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver;
Définir les données
Le code suivant crée les données pour le programme.
Python
costs = [ [90, 76, 75, 70, 50, 74], [35, 85, 55, 65, 48, 101], [125, 95, 90, 105, 59, 120], [45, 110, 95, 115, 104, 83], [60, 105, 80, 75, 59, 62], [45, 65, 110, 95, 47, 31], [38, 51, 107, 41, 69, 99], [47, 85, 57, 71, 92, 77], [39, 63, 97, 49, 118, 56], [47, 101, 71, 60, 88, 109], [17, 39, 103, 64, 61, 92], [101, 45, 83, 59, 92, 27], ] num_workers = len(costs) num_tasks = len(costs[0])
C++
const std::vector<std::vector<int64_t>> costs = {{ {{90, 76, 75, 70, 50, 74}}, {{35, 85, 55, 65, 48, 101}}, {{125, 95, 90, 105, 59, 120}}, {{45, 110, 95, 115, 104, 83}}, {{60, 105, 80, 75, 59, 62}}, {{45, 65, 110, 95, 47, 31}}, {{38, 51, 107, 41, 69, 99}}, {{47, 85, 57, 71, 92, 77}}, {{39, 63, 97, 49, 118, 56}}, {{47, 101, 71, 60, 88, 109}}, {{17, 39, 103, 64, 61, 92}}, {{101, 45, 83, 59, 92, 27}}, }}; const int num_workers = costs.size(); std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = costs[0].size(); std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0);
Java
double[][] costs = { {90, 76, 75, 70, 50, 74}, {35, 85, 55, 65, 48, 101}, {125, 95, 90, 105, 59, 120}, {45, 110, 95, 115, 104, 83}, {60, 105, 80, 75, 59, 62}, {45, 65, 110, 95, 47, 31}, {38, 51, 107, 41, 69, 99}, {47, 85, 57, 71, 92, 77}, {39, 63, 97, 49, 118, 56}, {47, 101, 71, 60, 88, 109}, {17, 39, 103, 64, 61, 92}, {101, 45, 83, 59, 92, 27}, }; int numWorkers = costs.length; int numTasks = costs[0].length; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray();
C#
int[,] costs = { { 90, 76, 75, 70, 50, 74 }, { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 }, { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 }, { 38, 51, 107, 41, 69, 99 }, { 47, 85, 57, 71, 92, 77 }, { 39, 63, 97, 49, 118, 56 }, { 47, 101, 71, 60, 88, 109 }, { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray();
Créer les groupes autorisés
Le code suivant crée les groupes autorisés en parcourant les trois ensembles de sous-groupes indiqués ci-dessus.
Python
group1 = [ # Subgroups of workers 0 - 3 [2, 3], [1, 3], [1, 2], [0, 1], [0, 2], ] group2 = [ # Subgroups of workers 4 - 7 [6, 7], [5, 7], [5, 6], [4, 5], [4, 7], ] group3 = [ # Subgroups of workers 8 - 11 [10, 11], [9, 11], [9, 10], [8, 10], [8, 11], ]
C++
using WorkerIndex = int; using Binome = std::pair<WorkerIndex, WorkerIndex>; using AllowedBinomes = std::vector<Binome>; const AllowedBinomes group1 = {{ // group of worker 0-3 {2, 3}, {1, 3}, {1, 2}, {0, 1}, {0, 2}, }}; const AllowedBinomes group2 = {{ // group of worker 4-7 {6, 7}, {5, 7}, {5, 6}, {4, 5}, {4, 7}, }}; const AllowedBinomes group3 = {{ // group of worker 8-11 {10, 11}, {9, 11}, {9, 10}, {8, 10}, {8, 11}, }};
Java
int[][] group1 = { // group of worker 0-3 {2, 3}, {1, 3}, {1, 2}, {0, 1}, {0, 2}, }; int[][] group2 = { // group of worker 4-7 {6, 7}, {5, 7}, {5, 6}, {4, 5}, {4, 7}, }; int[][] group3 = { // group of worker 8-11 {10, 11}, {9, 11}, {9, 10}, {8, 10}, {8, 11}, };
C#
int[,] group1 = { // group of worker 0-3 { 2, 3 }, { 1, 3 }, { 1, 2 }, { 0, 1 }, { 0, 2 }, }; int[,] group2 = { // group of worker 4-7 { 6, 7 }, { 5, 7 }, { 5, 6 }, { 4, 5 }, { 4, 7 }, }; int[,] group3 = { // group of worker 8-11 { 10, 11 }, { 9, 11 }, { 9, 10 }, { 8, 10 }, { 8, 11 }, };
Déclarer le résolveur
Le code suivant crée le résolveur.
Python
# Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver("SCIP") if not solver: return
C++
// Create the mip solver with the SCIP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP")); if (!solver) { LOG(WARNING) << "SCIP solver unavailable."; return; }
Java
// Create the linear solver with the SCIP backend. MPSolver solver = MPSolver.createSolver("SCIP"); if (solver == null) { System.out.println("Could not create solver SCIP"); return; }
C#
Solver solver = Solver.CreateSolver("SCIP"); if (solver is null) { return; }
Créer les variables
Le code suivant crée un tableau de variables pour le problème.
Python
# x[worker, task] is an array of 0-1 variables, which will be 1 # if the worker is assigned to the task. x = {} for worker in range(num_workers): for task in range(num_tasks): x[worker, task] = solver.BoolVar(f"x[{worker},{task}]")
C++
// x[i][j] is an array of 0-1 variables, which will be 1 // if worker i is assigned to task j. std::vector<std::vector<const MPVariable*>> x( num_workers, std::vector<const MPVariable*>(num_tasks)); for (int worker : all_workers) { for (int task : all_tasks) { x[worker][task] = solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task)); } }
Java
// x[i][j] is an array of 0-1 variables, which will be 1 // if worker i is assigned to task j. MPVariable[][] x = new MPVariable[numWorkers][numTasks]; for (int worker : allWorkers) { for (int task : allTasks) { x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]"); } }
C#
// x[i, j] is an array of 0-1 variables, which will be 1 // if worker i is assigned to task j. Variable[,] x = new Variable[numWorkers, numTasks]; foreach (int worker in allWorkers) { foreach (int task in allTasks) { x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]"); } }
Ajouter les contraintes
Le code suivant crée les contraintes du programme.
Python
# The total size of the tasks each worker takes on is at most total_size_max. for worker in range(num_workers): solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1) # Each task is assigned to exactly one worker. for task in range(num_tasks): solver.Add(solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1)
C++
// Each worker is assigned to at most one task. for (int worker : all_workers) { LinearExpr worker_sum; for (int task : all_tasks) { worker_sum += x[worker][task]; } solver->MakeRowConstraint(worker_sum <= 1.0); } // Each task is assigned to exactly one worker. for (int task : all_tasks) { LinearExpr task_sum; for (int worker : all_workers) { task_sum += x[worker][task]; } solver->MakeRowConstraint(task_sum == 1.0); }
Java
// Each worker is assigned to at most one task. for (int worker : allWorkers) { MPConstraint constraint = solver.makeConstraint(0, 1, ""); for (int task : allTasks) { constraint.setCoefficient(x[worker][task], 1); } } // Each task is assigned to exactly one worker. for (int task : allTasks) { MPConstraint constraint = solver.makeConstraint(1, 1, ""); for (int worker : allWorkers) { constraint.setCoefficient(x[worker][task], 1); } }
C#
// Each worker is assigned to at most one task. foreach (int worker in allWorkers) { Constraint constraint = solver.MakeConstraint(0, 1, ""); foreach (int task in allTasks) { constraint.SetCoefficient(x[worker, task], 1); } } // Each task is assigned to exactly one worker. foreach (int task in allTasks) { Constraint constraint = solver.MakeConstraint(1, 1, ""); foreach (int worker in allWorkers) { constraint.SetCoefficient(x[worker, task], 1); } }
Créer l'objectif
Le code suivant crée la fonction objectif.
Python
objective_terms = [] for worker in range(num_workers): for task in range(num_tasks): objective_terms.append(costs[worker][task] * x[worker, task]) solver.Minimize(solver.Sum(objective_terms))
C++
MPObjective* const objective = solver->MutableObjective(); for (int worker : all_workers) { for (int task : all_tasks) { objective->SetCoefficient(x[worker][task], costs[worker][task]); } } objective->SetMinimization();
Java
MPObjective objective = solver.objective(); for (int worker : allWorkers) { for (int task : allTasks) { objective.setCoefficient(x[worker][task], costs[worker][task]); } } objective.setMinimization();
C#
Objective objective = solver.Objective(); foreach (int worker in allWorkers) { foreach (int task in allTasks) { objective.SetCoefficient(x[worker, task], costs[worker, task]); } } objective.SetMinimization();
Appeler le résolveur
Le code suivant appelle le résolveur et affiche les résultats.
Python
print(f"Solving with {solver.SolverVersion()}") status = solver.Solve()
C++
const MPSolver::ResultStatus result_status = solver->Solve();
Java
MPSolver.ResultStatus resultStatus = solver.solve();
C#
Solver.ResultStatus resultStatus = solver.Solve();
Afficher les résultats
Nous pouvons maintenant imprimer la solution.
Python
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE: print(f"Total cost = {solver.Objective().Value()}\n") for worker in range(num_workers): for task in range(num_tasks): if x[worker, task].solution_value() > 0.5: print( f"Worker {worker} assigned to task {task}." + f" Cost: {costs[worker][task]}" ) else: print("No solution found.")
C++
// Check that the problem has a feasible solution. if (result_status != MPSolver::OPTIMAL && result_status != MPSolver::FEASIBLE) { LOG(FATAL) << "No solution found."; } LOG(INFO) << "Total cost = " << objective->Value() << "\n\n"; for (int worker : all_workers) { for (int task : all_tasks) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[worker][task]->solution_value() > 0.5) { LOG(INFO) << "Worker " << worker << " assigned to task " << task << ". Cost: " << costs[worker][task]; } } }
Java
// Check that the problem has a feasible solution. if (resultStatus == MPSolver.ResultStatus.OPTIMAL || resultStatus == MPSolver.ResultStatus.FEASIBLE) { System.out.println("Total cost: " + objective.value() + "\n"); for (int worker : allWorkers) { for (int task : allTasks) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[worker][task].solutionValue() > 0.5) { System.out.println("Worker " + worker + " assigned to task " + task + ". Cost: " + costs[worker][task]); } } } } else { System.err.println("No solution found."); }
C#
// Check that the problem has a feasible solution. if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE) { Console.WriteLine($"Total cost: {solver.Objective().Value()}\n"); foreach (int worker in allWorkers) { foreach (int task in allTasks) { // Test if x[i, j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[worker, task].SolutionValue() > 0.5) { Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}"); } } } } else { Console.WriteLine("No solution found."); }
Voici la sortie du programme:
Minimum cost = 239.0 Worker 0 assigned to task 4 Cost = 50 Worker 1 assigned to task 2 Cost = 55 Worker 5 assigned to task 5 Cost = 31 Worker 6 assigned to task 3 Cost = 41 Worker 10 assigned to task 0 Cost = 17 Worker 11 assigned to task 1 Cost = 45 Time = 0.3281 seconds
L'ensemble du programme
Voici le programme complet.
Python
"""Solve assignment problem for given group of workers.""" from ortools.linear_solver import pywraplp def main(): # Data costs = [ [90, 76, 75, 70, 50, 74], [35, 85, 55, 65, 48, 101], [125, 95, 90, 105, 59, 120], [45, 110, 95, 115, 104, 83], [60, 105, 80, 75, 59, 62], [45, 65, 110, 95, 47, 31], [38, 51, 107, 41, 69, 99], [47, 85, 57, 71, 92, 77], [39, 63, 97, 49, 118, 56], [47, 101, 71, 60, 88, 109], [17, 39, 103, 64, 61, 92], [101, 45, 83, 59, 92, 27], ] num_workers = len(costs) num_tasks = len(costs[0]) # Allowed groups of workers: group1 = [ # Subgroups of workers 0 - 3 [2, 3], [1, 3], [1, 2], [0, 1], [0, 2], ] group2 = [ # Subgroups of workers 4 - 7 [6, 7], [5, 7], [5, 6], [4, 5], [4, 7], ] group3 = [ # Subgroups of workers 8 - 11 [10, 11], [9, 11], [9, 10], [8, 10], [8, 11], ] # Solver. # Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver("SCIP") if not solver: return # Variables # x[worker, task] is an array of 0-1 variables, which will be 1 # if the worker is assigned to the task. x = {} for worker in range(num_workers): for task in range(num_tasks): x[worker, task] = solver.BoolVar(f"x[{worker},{task}]") # Constraints # The total size of the tasks each worker takes on is at most total_size_max. for worker in range(num_workers): solver.Add(solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1) # Each task is assigned to exactly one worker. for task in range(num_tasks): solver.Add(solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1) # Create variables for each worker, indicating whether they work on some task. work = {} for worker in range(num_workers): work[worker] = solver.BoolVar(f"work[{worker}]") for worker in range(num_workers): solver.Add( work[worker] == solver.Sum([x[worker, task] for task in range(num_tasks)]) ) # Group1 constraint_g1 = solver.Constraint(1, 1) for index, _ in enumerate(group1): # a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] # p is True if a AND b, False otherwise constraint = solver.Constraint(0, 1) constraint.SetCoefficient(work[group1[index][0]], 1) constraint.SetCoefficient(work[group1[index][1]], 1) p = solver.BoolVar(f"g1_p{index}") constraint.SetCoefficient(p, -2) constraint_g1.SetCoefficient(p, 1) # Group2 constraint_g2 = solver.Constraint(1, 1) for index, _ in enumerate(group2): # a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] # p is True if a AND b, False otherwise constraint = solver.Constraint(0, 1) constraint.SetCoefficient(work[group2[index][0]], 1) constraint.SetCoefficient(work[group2[index][1]], 1) p = solver.BoolVar(f"g2_p{index}") constraint.SetCoefficient(p, -2) constraint_g2.SetCoefficient(p, 1) # Group3 constraint_g3 = solver.Constraint(1, 1) for index, _ in enumerate(group3): # a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] # p is True if a AND b, False otherwise constraint = solver.Constraint(0, 1) constraint.SetCoefficient(work[group3[index][0]], 1) constraint.SetCoefficient(work[group3[index][1]], 1) p = solver.BoolVar(f"g3_p{index}") constraint.SetCoefficient(p, -2) constraint_g3.SetCoefficient(p, 1) # Objective objective_terms = [] for worker in range(num_workers): for task in range(num_tasks): objective_terms.append(costs[worker][task] * x[worker, task]) solver.Minimize(solver.Sum(objective_terms)) # Solve print(f"Solving with {solver.SolverVersion()}") status = solver.Solve() # Print solution. if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE: print(f"Total cost = {solver.Objective().Value()}\n") for worker in range(num_workers): for task in range(num_tasks): if x[worker, task].solution_value() > 0.5: print( f"Worker {worker} assigned to task {task}." + f" Cost: {costs[worker][task]}" ) else: print("No solution found.") if __name__ == "__main__": main()
C++
// Solve a simple assignment problem. #include <cstdint> #include <memory> #include <numeric> #include <utility> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/linear_solver/linear_solver.h" namespace operations_research { void AssignmentTeamsMip() { // Data const std::vector<std::vector<int64_t>> costs = {{ {{90, 76, 75, 70, 50, 74}}, {{35, 85, 55, 65, 48, 101}}, {{125, 95, 90, 105, 59, 120}}, {{45, 110, 95, 115, 104, 83}}, {{60, 105, 80, 75, 59, 62}}, {{45, 65, 110, 95, 47, 31}}, {{38, 51, 107, 41, 69, 99}}, {{47, 85, 57, 71, 92, 77}}, {{39, 63, 97, 49, 118, 56}}, {{47, 101, 71, 60, 88, 109}}, {{17, 39, 103, 64, 61, 92}}, {{101, 45, 83, 59, 92, 27}}, }}; const int num_workers = costs.size(); std::vector<int> all_workers(num_workers); std::iota(all_workers.begin(), all_workers.end(), 0); const int num_tasks = costs[0].size(); std::vector<int> all_tasks(num_tasks); std::iota(all_tasks.begin(), all_tasks.end(), 0); // Allowed groups of workers: using WorkerIndex = int; using Binome = std::pair<WorkerIndex, WorkerIndex>; using AllowedBinomes = std::vector<Binome>; const AllowedBinomes group1 = {{ // group of worker 0-3 {2, 3}, {1, 3}, {1, 2}, {0, 1}, {0, 2}, }}; const AllowedBinomes group2 = {{ // group of worker 4-7 {6, 7}, {5, 7}, {5, 6}, {4, 5}, {4, 7}, }}; const AllowedBinomes group3 = {{ // group of worker 8-11 {10, 11}, {9, 11}, {9, 10}, {8, 10}, {8, 11}, }}; // Solver // Create the mip solver with the SCIP backend. std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP")); if (!solver) { LOG(WARNING) << "SCIP solver unavailable."; return; } // Variables // x[i][j] is an array of 0-1 variables, which will be 1 // if worker i is assigned to task j. std::vector<std::vector<const MPVariable*>> x( num_workers, std::vector<const MPVariable*>(num_tasks)); for (int worker : all_workers) { for (int task : all_tasks) { x[worker][task] = solver->MakeBoolVar(absl::StrFormat("x[%d,%d]", worker, task)); } } // Constraints // Each worker is assigned to at most one task. for (int worker : all_workers) { LinearExpr worker_sum; for (int task : all_tasks) { worker_sum += x[worker][task]; } solver->MakeRowConstraint(worker_sum <= 1.0); } // Each task is assigned to exactly one worker. for (int task : all_tasks) { LinearExpr task_sum; for (int worker : all_workers) { task_sum += x[worker][task]; } solver->MakeRowConstraint(task_sum == 1.0); } // Create variables for each worker, indicating whether they work on some // task. std::vector<const MPVariable*> work(num_workers); for (int worker : all_workers) { work[worker] = solver->MakeBoolVar(absl::StrFormat("work[%d]", worker)); } for (int worker : all_workers) { LinearExpr task_sum; for (int task : all_tasks) { task_sum += x[worker][task]; } solver->MakeRowConstraint(work[worker] == task_sum); } // Group1 { MPConstraint* g1 = solver->MakeRowConstraint(1, 1); for (int i = 0; i < group1.size(); ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is true if a AND b, false otherwise MPConstraint* tmp = solver->MakeRowConstraint(0, 1); tmp->SetCoefficient(work[group1[i].first], 1); tmp->SetCoefficient(work[group1[i].second], 1); MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g1_p%d", i)); tmp->SetCoefficient(p, -2); g1->SetCoefficient(p, 1); } } // Group2 { MPConstraint* g2 = solver->MakeRowConstraint(1, 1); for (int i = 0; i < group2.size(); ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is true if a AND b, false otherwise MPConstraint* tmp = solver->MakeRowConstraint(0, 1); tmp->SetCoefficient(work[group2[i].first], 1); tmp->SetCoefficient(work[group2[i].second], 1); MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g2_p%d", i)); tmp->SetCoefficient(p, -2); g2->SetCoefficient(p, 1); } } // Group3 { MPConstraint* g3 = solver->MakeRowConstraint(1, 1); for (int i = 0; i < group3.size(); ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is true if a AND b, false otherwise MPConstraint* tmp = solver->MakeRowConstraint(0, 1); tmp->SetCoefficient(work[group3[i].first], 1); tmp->SetCoefficient(work[group3[i].second], 1); MPVariable* p = solver->MakeBoolVar(absl::StrFormat("g3_p%d", i)); tmp->SetCoefficient(p, -2); g3->SetCoefficient(p, 1); } } // Objective. MPObjective* const objective = solver->MutableObjective(); for (int worker : all_workers) { for (int task : all_tasks) { objective->SetCoefficient(x[worker][task], costs[worker][task]); } } objective->SetMinimization(); // Solve const MPSolver::ResultStatus result_status = solver->Solve(); // Print solution. // Check that the problem has a feasible solution. if (result_status != MPSolver::OPTIMAL && result_status != MPSolver::FEASIBLE) { LOG(FATAL) << "No solution found."; } LOG(INFO) << "Total cost = " << objective->Value() << "\n\n"; for (int worker : all_workers) { for (int task : all_tasks) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[worker][task]->solution_value() > 0.5) { LOG(INFO) << "Worker " << worker << " assigned to task " << task << ". Cost: " << costs[worker][task]; } } } } } // namespace operations_research int main(int argc, char** argv) { operations_research::AssignmentTeamsMip(); return EXIT_SUCCESS; }
Java
package com.google.ortools.linearsolver.samples; import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable; import java.util.stream.IntStream; /** MIP example that solves an assignment problem. */ public class AssignmentGroupsMip { public static void main(String[] args) { Loader.loadNativeLibraries(); // Data double[][] costs = { {90, 76, 75, 70, 50, 74}, {35, 85, 55, 65, 48, 101}, {125, 95, 90, 105, 59, 120}, {45, 110, 95, 115, 104, 83}, {60, 105, 80, 75, 59, 62}, {45, 65, 110, 95, 47, 31}, {38, 51, 107, 41, 69, 99}, {47, 85, 57, 71, 92, 77}, {39, 63, 97, 49, 118, 56}, {47, 101, 71, 60, 88, 109}, {17, 39, 103, 64, 61, 92}, {101, 45, 83, 59, 92, 27}, }; int numWorkers = costs.length; int numTasks = costs[0].length; final int[] allWorkers = IntStream.range(0, numWorkers).toArray(); final int[] allTasks = IntStream.range(0, numTasks).toArray(); // Allowed groups of workers: int[][] group1 = { // group of worker 0-3 {2, 3}, {1, 3}, {1, 2}, {0, 1}, {0, 2}, }; int[][] group2 = { // group of worker 4-7 {6, 7}, {5, 7}, {5, 6}, {4, 5}, {4, 7}, }; int[][] group3 = { // group of worker 8-11 {10, 11}, {9, 11}, {9, 10}, {8, 10}, {8, 11}, }; // Solver // Create the linear solver with the SCIP backend. MPSolver solver = MPSolver.createSolver("SCIP"); if (solver == null) { System.out.println("Could not create solver SCIP"); return; } // Variables // x[i][j] is an array of 0-1 variables, which will be 1 // if worker i is assigned to task j. MPVariable[][] x = new MPVariable[numWorkers][numTasks]; for (int worker : allWorkers) { for (int task : allTasks) { x[worker][task] = solver.makeBoolVar("x[" + worker + "," + task + "]"); } } // Constraints // Each worker is assigned to at most one task. for (int worker : allWorkers) { MPConstraint constraint = solver.makeConstraint(0, 1, ""); for (int task : allTasks) { constraint.setCoefficient(x[worker][task], 1); } } // Each task is assigned to exactly one worker. for (int task : allTasks) { MPConstraint constraint = solver.makeConstraint(1, 1, ""); for (int worker : allWorkers) { constraint.setCoefficient(x[worker][task], 1); } } // Create variables for each worker, indicating whether they work on some task. MPVariable[] work = new MPVariable[numWorkers]; for (int worker : allWorkers) { work[worker] = solver.makeBoolVar("work[" + worker + "]"); } for (int worker : allWorkers) { // MPVariable[] vars = new MPVariable[numTasks]; MPConstraint constraint = solver.makeConstraint(0, 0, ""); for (int task : allTasks) { // vars[task] = x[worker][task]; constraint.setCoefficient(x[worker][task], 1); } // solver.addEquality(work[worker], LinearExpr.sum(vars)); constraint.setCoefficient(work[worker], -1); } // Group1 MPConstraint constraintG1 = solver.makeConstraint(1, 1, ""); for (int i = 0; i < group1.length; ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is True if a AND b, False otherwise MPConstraint constraint = solver.makeConstraint(0, 1, ""); constraint.setCoefficient(work[group1[i][0]], 1); constraint.setCoefficient(work[group1[i][1]], 1); MPVariable p = solver.makeBoolVar("g1_p" + i); constraint.setCoefficient(p, -2); constraintG1.setCoefficient(p, 1); } // Group2 MPConstraint constraintG2 = solver.makeConstraint(1, 1, ""); for (int i = 0; i < group2.length; ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is True if a AND b, False otherwise MPConstraint constraint = solver.makeConstraint(0, 1, ""); constraint.setCoefficient(work[group2[i][0]], 1); constraint.setCoefficient(work[group2[i][1]], 1); MPVariable p = solver.makeBoolVar("g2_p" + i); constraint.setCoefficient(p, -2); constraintG2.setCoefficient(p, 1); } // Group3 MPConstraint constraintG3 = solver.makeConstraint(1, 1, ""); for (int i = 0; i < group3.length; ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is True if a AND b, False otherwise MPConstraint constraint = solver.makeConstraint(0, 1, ""); constraint.setCoefficient(work[group3[i][0]], 1); constraint.setCoefficient(work[group3[i][1]], 1); MPVariable p = solver.makeBoolVar("g3_p" + i); constraint.setCoefficient(p, -2); constraintG3.setCoefficient(p, 1); } // Objective MPObjective objective = solver.objective(); for (int worker : allWorkers) { for (int task : allTasks) { objective.setCoefficient(x[worker][task], costs[worker][task]); } } objective.setMinimization(); // Solve MPSolver.ResultStatus resultStatus = solver.solve(); // Print solution. // Check that the problem has a feasible solution. if (resultStatus == MPSolver.ResultStatus.OPTIMAL || resultStatus == MPSolver.ResultStatus.FEASIBLE) { System.out.println("Total cost: " + objective.value() + "\n"); for (int worker : allWorkers) { for (int task : allTasks) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[worker][task].solutionValue() > 0.5) { System.out.println("Worker " + worker + " assigned to task " + task + ". Cost: " + costs[worker][task]); } } } } else { System.err.println("No solution found."); } } private AssignmentGroupsMip() {} }
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver; public class AssignmentGroupsMip { static void Main() { // Data. int[,] costs = { { 90, 76, 75, 70, 50, 74 }, { 35, 85, 55, 65, 48, 101 }, { 125, 95, 90, 105, 59, 120 }, { 45, 110, 95, 115, 104, 83 }, { 60, 105, 80, 75, 59, 62 }, { 45, 65, 110, 95, 47, 31 }, { 38, 51, 107, 41, 69, 99 }, { 47, 85, 57, 71, 92, 77 }, { 39, 63, 97, 49, 118, 56 }, { 47, 101, 71, 60, 88, 109 }, { 17, 39, 103, 64, 61, 92 }, { 101, 45, 83, 59, 92, 27 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); // Allowed groups of workers: int[,] group1 = { // group of worker 0-3 { 2, 3 }, { 1, 3 }, { 1, 2 }, { 0, 1 }, { 0, 2 }, }; int[,] group2 = { // group of worker 4-7 { 6, 7 }, { 5, 7 }, { 5, 6 }, { 4, 5 }, { 4, 7 }, }; int[,] group3 = { // group of worker 8-11 { 10, 11 }, { 9, 11 }, { 9, 10 }, { 8, 10 }, { 8, 11 }, }; // Solver. Solver solver = Solver.CreateSolver("SCIP"); if (solver is null) { return; } // Variables. // x[i, j] is an array of 0-1 variables, which will be 1 // if worker i is assigned to task j. Variable[,] x = new Variable[numWorkers, numTasks]; foreach (int worker in allWorkers) { foreach (int task in allTasks) { x[worker, task] = solver.MakeBoolVar($"x[{worker},{task}]"); } } // Constraints // Each worker is assigned to at most one task. foreach (int worker in allWorkers) { Constraint constraint = solver.MakeConstraint(0, 1, ""); foreach (int task in allTasks) { constraint.SetCoefficient(x[worker, task], 1); } } // Each task is assigned to exactly one worker. foreach (int task in allTasks) { Constraint constraint = solver.MakeConstraint(1, 1, ""); foreach (int worker in allWorkers) { constraint.SetCoefficient(x[worker, task], 1); } } // Create variables for each worker, indicating whether they work on some task. Variable[] work = new Variable[numWorkers]; foreach (int worker in allWorkers) { work[worker] = solver.MakeBoolVar($"work[{worker}]"); } foreach (int worker in allWorkers) { Variable[] vars = new Variable[numTasks]; foreach (int task in allTasks) { vars[task] = x[worker, task]; } solver.Add(work[worker] == LinearExprArrayHelper.Sum(vars)); } // Group1 Constraint constraint_g1 = solver.MakeConstraint(1, 1, ""); for (int i = 0; i < group1.GetLength(0); ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is True if a AND b, False otherwise Constraint constraint = solver.MakeConstraint(0, 1, ""); constraint.SetCoefficient(work[group1[i, 0]], 1); constraint.SetCoefficient(work[group1[i, 1]], 1); Variable p = solver.MakeBoolVar($"g1_p{i}"); constraint.SetCoefficient(p, -2); constraint_g1.SetCoefficient(p, 1); } // Group2 Constraint constraint_g2 = solver.MakeConstraint(1, 1, ""); for (int i = 0; i < group2.GetLength(0); ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is True if a AND b, False otherwise Constraint constraint = solver.MakeConstraint(0, 1, ""); constraint.SetCoefficient(work[group2[i, 0]], 1); constraint.SetCoefficient(work[group2[i, 1]], 1); Variable p = solver.MakeBoolVar($"g2_p{i}"); constraint.SetCoefficient(p, -2); constraint_g2.SetCoefficient(p, 1); } // Group3 Constraint constraint_g3 = solver.MakeConstraint(1, 1, ""); for (int i = 0; i < group3.GetLength(0); ++i) { // a*b can be transformed into 0 <= a + b - 2*p <= 1 with p in [0,1] // p is True if a AND b, False otherwise Constraint constraint = solver.MakeConstraint(0, 1, ""); constraint.SetCoefficient(work[group3[i, 0]], 1); constraint.SetCoefficient(work[group3[i, 1]], 1); Variable p = solver.MakeBoolVar($"g3_p{i}"); constraint.SetCoefficient(p, -2); constraint_g3.SetCoefficient(p, 1); } // Objective Objective objective = solver.Objective(); foreach (int worker in allWorkers) { foreach (int task in allTasks) { objective.SetCoefficient(x[worker, task], costs[worker, task]); } } objective.SetMinimization(); // Solve Solver.ResultStatus resultStatus = solver.Solve(); // Print solution. // Check that the problem has a feasible solution. if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE) { Console.WriteLine($"Total cost: {solver.Objective().Value()}\n"); foreach (int worker in allWorkers) { foreach (int task in allTasks) { // Test if x[i, j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[worker, task].SolutionValue() > 0.5) { Console.WriteLine($"Worker {worker} assigned to task {task}. Cost: {costs[worker, task]}"); } } } } else { Console.WriteLine("No solution found."); } } }
Horaires des solutions
Les temps de solution des deux résolveurs sont les suivants:
- CP-SAT: 0,0113 secondes
- MIP: 0,3281 seconde
CP-SAT est beaucoup plus rapide que MIP pour ce problème.