AI-generated Key Takeaways
-
The code addresses the Generalized Assignment Problem, optimizing task assignments to workers with varying costs and sizes to minimize total cost.
-
Solutions are presented using Constraint Programming (CP) and Mixed Integer Programming (MIP) approaches, ensuring each task is assigned to one worker and respecting worker capacity limits.
-
Code examples in Python, C++, Java, and C# demonstrate data definition, model creation, constraint implementation, and solver invocation for practical problem-solving.
-
The output showcases the optimal or feasible assignment of workers to tasks, along with the minimum cost achieved, illustrating successful problem resolution.
This section describes an assignment problem in which each task has a size, which represents how much time or effort the task requires. The total size of the tasks performed by each worker has a fixed bound.
We'll present Python programs that solve this problem using the CP-SAT solver and the MIP solver.
CP-SAT solution
First, let's take a look at the CP-SAT solution to the problem.
Import the libraries
The following code imports the required library.
Python
from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <cstdint> #include <numeric> #include <vector> #include "absl/base/log_severity.h" #include "absl/log/globals.h" #include "absl/strings/str_format.h" #include "ortools/base/init_google.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.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;
Define the data
The following code creates the data for the program.
Python
costs = [ [90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90], ] num_workers = len(costs) num_tasks = len(costs[0]) task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15
C++
const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70, 50, 74, 12, 68}}, {{35, 85, 55, 65, 48, 101, 70, 83}}, {{125, 95, 90, 105, 59, 120, 36, 73}}, {{45, 110, 95, 115, 104, 83, 37, 71}}, {{60, 105, 80, 75, 59, 62, 93, 88}}, {{45, 65, 110, 95, 47, 31, 81, 34}}, {{38, 51, 107, 41, 69, 99, 115, 48}}, {{47, 85, 57, 71, 92, 77, 109, 36}}, {{39, 63, 97, 49, 118, 56, 92, 61}}, {{47, 101, 71, 60, 88, 109, 52, 90}}, }}; 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); const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}}; // Maximum total of task sizes for any worker const int total_size_max = 15;
Java
int[][] costs = { {90, 76, 75, 70, 50, 74, 12, 68}, {35, 85, 55, 65, 48, 101, 70, 83}, {125, 95, 90, 105, 59, 120, 36, 73}, {45, 110, 95, 115, 104, 83, 37, 71}, {60, 105, 80, 75, 59, 62, 93, 88}, {45, 65, 110, 95, 47, 31, 81, 34}, {38, 51, 107, 41, 69, 99, 115, 48}, {47, 85, 57, 71, 92, 77, 109, 36}, {39, 63, 97, 49, 118, 56, 92, 61}, {47, 101, 71, 60, 88, 109, 52, 90}, }; 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(); final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5}; // Maximum total of task sizes for any worker final int totalSizeMax = 15;
C#
int[,] costs = { { 90, 76, 75, 70, 50, 74, 12, 68 }, { 35, 85, 55, 65, 48, 101, 70, 83 }, { 125, 95, 90, 105, 59, 120, 36, 73 }, { 45, 110, 95, 115, 104, 83, 37, 71 }, { 60, 105, 80, 75, 59, 62, 93, 88 }, { 45, 65, 110, 95, 47, 31, 81, 34 }, { 38, 51, 107, 41, 69, 99, 115, 48 }, { 47, 85, 57, 71, 92, 77, 109, 36 }, { 39, 63, 97, 49, 118, 56, 92, 61 }, { 47, 101, 71, 60, 88, 109, 52, 90 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 }; // Maximum total of task sizes for any worker int totalSizeMax = 15;
As in previous examples, the
cost matrix
gives the cost for worker i
to perform task j
.
The sizes
vector gives the size of each task.
total_size_max
is the upper bound on the total size of the tasks
performed by any single worker.
Create the model
The following code creates the model.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Create the variables
The following code creates an array of variables for the problem.
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]; foreach (int worker in allWorkers) { foreach (int task in allTasks) { x[worker, task] = model.NewBoolVar($"x[{worker},{task}]"); } }
Add the constraints
The following code creates the constraints for the program.
Python
# Each worker is assigned to at most one task. for worker in range(num_workers): model.add( sum(task_sizes[task] * x[worker, task] for task in range(num_tasks)) <= total_size_max ) # 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) { LinearExpr task_sum; for (int task : all_tasks) { task_sum += x[worker][task] * task_sizes[task]; } cp_model.AddLessOrEqual(task_sum, total_size_max); } // 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 has a maximum capacity. for (int worker : allWorkers) { LinearExprBuilder expr = LinearExpr.newBuilder(); for (int task : allTasks) { expr.addTerm(x[worker][task], taskSizes[task]); } model.addLessOrEqual(expr, totalSizeMax); } // 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 max task size. foreach (int worker in allWorkers) { BoolVar[] vars = new BoolVar[numTasks]; foreach (int task in allTasks) { vars[task] = x[worker, task]; } model.Add(LinearExpr.WeightedSum(vars, taskSizes) <= totalSizeMax); } // 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 the objective
The following code creates the objective function.
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);
Invoke the solver
The following code invokes the solver.
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}");
Display the results
Now, we can print the 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."); }
Here's the output of the program.
Minimum cost: 326 Worker 0 assigned to task 6 Cost = 12 Worker 1 assigned to task 0 Cost = 35 Worker 1 assigned to task 2 Cost = 55 Worker 2 assigned to task 4 Cost = 59 Worker 5 assigned to task 5 Cost = 31 Worker 5 assigned to task 7 Cost = 34 Worker 6 assigned to task 1 Cost = 51 Worker 8 assigned to task 3 Cost = 49 Time = 2.2198 seconds
The entire program
Here is the entire program.
Python
"""Solves a simple assignment problem.""" from ortools.sat.python import cp_model def main() -> None: # Data costs = [ [90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90], ] num_workers = len(costs) num_tasks = len(costs[0]) task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15 # 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( sum(task_sizes[task] * x[worker, task] for task in range(num_tasks)) <= total_size_max ) # 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)) # 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. #include <stdlib.h> #include <cstdint> #include <numeric> #include <vector> #include "absl/base/log_severity.h" #include "absl/log/globals.h" #include "absl/strings/str_format.h" #include "ortools/base/init_google.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 AssignmentTaskSizes() { // Data const std::vector<std::vector<int>> costs = {{ {{90, 76, 75, 70, 50, 74, 12, 68}}, {{35, 85, 55, 65, 48, 101, 70, 83}}, {{125, 95, 90, 105, 59, 120, 36, 73}}, {{45, 110, 95, 115, 104, 83, 37, 71}}, {{60, 105, 80, 75, 59, 62, 93, 88}}, {{45, 65, 110, 95, 47, 31, 81, 34}}, {{38, 51, 107, 41, 69, 99, 115, 48}}, {{47, 85, 57, 71, 92, 77, 109, 36}}, {{39, 63, 97, 49, 118, 56, 92, 61}}, {{47, 101, 71, 60, 88, 109, 52, 90}}, }}; 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); const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}}; // Maximum total of task sizes for any worker const int total_size_max = 15; // 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) { LinearExpr task_sum; for (int task : all_tasks) { task_sum += x[worker][task] * task_sizes[task]; } cp_model.AddLessOrEqual(task_sum, total_size_max); } // 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); } // 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[]) { InitGoogle(argv[0], &argc, &argv, true); absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo); operations_research::sat::AssignmentTaskSizes(); 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.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 AssignmentTaskSizesSat { public static void main(String[] args) { Loader.loadNativeLibraries(); // Data int[][] costs = { {90, 76, 75, 70, 50, 74, 12, 68}, {35, 85, 55, 65, 48, 101, 70, 83}, {125, 95, 90, 105, 59, 120, 36, 73}, {45, 110, 95, 115, 104, 83, 37, 71}, {60, 105, 80, 75, 59, 62, 93, 88}, {45, 65, 110, 95, 47, 31, 81, 34}, {38, 51, 107, 41, 69, 99, 115, 48}, {47, 85, 57, 71, 92, 77, 109, 36}, {39, 63, 97, 49, 118, 56, 92, 61}, {47, 101, 71, 60, 88, 109, 52, 90}, }; 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(); final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5}; // Maximum total of task sizes for any worker final int totalSizeMax = 15; // 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 has a maximum capacity. for (int worker : allWorkers) { LinearExprBuilder expr = LinearExpr.newBuilder(); for (int task : allTasks) { expr.addTerm(x[worker][task], taskSizes[task]); } model.addLessOrEqual(expr, totalSizeMax); } // 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); } // 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 AssignmentTaskSizesSat() {} }
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.Sat; public class AssignmentTaskSizesSat { public static void Main(String[] args) { // Data. int[,] costs = { { 90, 76, 75, 70, 50, 74, 12, 68 }, { 35, 85, 55, 65, 48, 101, 70, 83 }, { 125, 95, 90, 105, 59, 120, 36, 73 }, { 45, 110, 95, 115, 104, 83, 37, 71 }, { 60, 105, 80, 75, 59, 62, 93, 88 }, { 45, 65, 110, 95, 47, 31, 81, 34 }, { 38, 51, 107, 41, 69, 99, 115, 48 }, { 47, 85, 57, 71, 92, 77, 109, 36 }, { 39, 63, 97, 49, 118, 56, 92, 61 }, { 47, 101, 71, 60, 88, 109, 52, 90 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 }; // Maximum total of task sizes for any worker int totalSizeMax = 15; // Model. CpModel model = new CpModel(); // Variables. BoolVar[,] x = new BoolVar[numWorkers, numTasks]; 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 max task size. foreach (int worker in allWorkers) { BoolVar[] vars = new BoolVar[numTasks]; foreach (int task in allTasks) { vars[task] = x[worker, task]; } model.Add(LinearExpr.WeightedSum(vars, taskSizes) <= totalSizeMax); } // 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); } // 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"); } }
MIP solution
Next, we describe a solution to the assignment problem using the MIP solver.
Import the libraries
The following code imports the required library.
Python
from ortools.linear_solver import pywraplp
C++
#include <cstdint> #include <memory> #include <numeric> #include <vector> #include "absl/base/log_severity.h" #include "absl/log/globals.h" #include "absl/strings/str_format.h" #include "ortools/base/init_google.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;
Define the data
The following code creates the data for the program.
Python
costs = [ [90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90], ] num_workers = len(costs) num_tasks = len(costs[0]) task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15
C++
const std::vector<std::vector<int64_t>> costs = {{ {{90, 76, 75, 70, 50, 74, 12, 68}}, {{35, 85, 55, 65, 48, 101, 70, 83}}, {{125, 95, 90, 105, 59, 120, 36, 73}}, {{45, 110, 95, 115, 104, 83, 37, 71}}, {{60, 105, 80, 75, 59, 62, 93, 88}}, {{45, 65, 110, 95, 47, 31, 81, 34}}, {{38, 51, 107, 41, 69, 99, 115, 48}}, {{47, 85, 57, 71, 92, 77, 109, 36}}, {{39, 63, 97, 49, 118, 56, 92, 61}}, {{47, 101, 71, 60, 88, 109, 52, 90}}, }}; 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); const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}}; // Maximum total of task sizes for any worker const int total_size_max = 15;
Java
double[][] costs = { {90, 76, 75, 70, 50, 74, 12, 68}, {35, 85, 55, 65, 48, 101, 70, 83}, {125, 95, 90, 105, 59, 120, 36, 73}, {45, 110, 95, 115, 104, 83, 37, 71}, {60, 105, 80, 75, 59, 62, 93, 88}, {45, 65, 110, 95, 47, 31, 81, 34}, {38, 51, 107, 41, 69, 99, 115, 48}, {47, 85, 57, 71, 92, 77, 109, 36}, {39, 63, 97, 49, 118, 56, 92, 61}, {47, 101, 71, 60, 88, 109, 52, 90}, }; 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(); final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5}; // Maximum total of task sizes for any worker final int totalSizeMax = 15;
C#
int[,] costs = { { 90, 76, 75, 70, 50, 74, 12, 68 }, { 35, 85, 55, 65, 48, 101, 70, 83 }, { 125, 95, 90, 105, 59, 120, 36, 73 }, { 45, 110, 95, 115, 104, 83, 37, 71 }, { 60, 105, 80, 75, 59, 62, 93, 88 }, { 45, 65, 110, 95, 47, 31, 81, 34 }, { 38, 51, 107, 41, 69, 99, 115, 48 }, { 47, 85, 57, 71, 92, 77, 109, 36 }, { 39, 63, 97, 49, 118, 56, 92, 61 }, { 47, 101, 71, 60, 88, 109, 52, 90 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 }; // Maximum total of task sizes for any worker int totalSizeMax = 15;
Declare the solver
The following code creates the solver.
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; }
Create the variables
The following code creates an array of variables for the problem.
Python
# x[i, j] is an array of 0-1 variables, which will be 1 # if worker i is assigned to task j. 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}]"); } }
Add the constraints
The following code creates the constraints for the program.
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( [task_sizes[task] * x[worker, task] for task in range(num_tasks)] ) <= total_size_max ) # 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 += LinearExpr(x[worker][task]) * task_sizes[task]; } solver->MakeRowConstraint(worker_sum <= total_size_max); } // 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 max task size. for (int worker : allWorkers) { MPConstraint constraint = solver.makeConstraint(0, totalSizeMax, ""); for (int task : allTasks) { constraint.setCoefficient(x[worker][task], taskSizes[task]); } } // 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 max task size. foreach (int worker in allWorkers) { Constraint constraint = solver.MakeConstraint(0, totalSizeMax, ""); foreach (int task in allTasks) { constraint.SetCoefficient(x[worker, task], taskSizes[task]); } } // 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 the objective
The following code creates the objective function.
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();
Invoke the solver
The following code invokes the solver and displays the results.
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();
Display the results
Now, we can print the 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."); }
Here is the output of the program.
Minimum cost = 326.0 Worker 0 assigned to task 6 Cost = 12 Worker 1 assigned to task 0 Cost = 35 Worker 1 assigned to task 2 Cost = 55 Worker 4 assigned to task 4 Cost = 59 Worker 5 assigned to task 5 Cost = 31 Worker 5 assigned to task 7 Cost = 34 Worker 6 assigned to task 1 Cost = 51 Worker 8 assigned to task 3 Cost = 49 Time = 0.0167 seconds
The entire program
Here is the entire program.
Python
"""MIP example that solves an assignment problem.""" from ortools.linear_solver import pywraplp def main(): # Data costs = [ [90, 76, 75, 70, 50, 74, 12, 68], [35, 85, 55, 65, 48, 101, 70, 83], [125, 95, 90, 105, 59, 120, 36, 73], [45, 110, 95, 115, 104, 83, 37, 71], [60, 105, 80, 75, 59, 62, 93, 88], [45, 65, 110, 95, 47, 31, 81, 34], [38, 51, 107, 41, 69, 99, 115, 48], [47, 85, 57, 71, 92, 77, 109, 36], [39, 63, 97, 49, 118, 56, 92, 61], [47, 101, 71, 60, 88, 109, 52, 90], ] num_workers = len(costs) num_tasks = len(costs[0]) task_sizes = [10, 7, 3, 12, 15, 4, 11, 5] # Maximum total of task sizes for any worker total_size_max = 15 # Solver # Create the mip solver with the SCIP backend. solver = pywraplp.Solver.CreateSolver("SCIP") if not solver: return # Variables # x[i, j] is an array of 0-1 variables, which will be 1 # if worker i is assigned to task j. 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( [task_sizes[task] * x[worker, task] for task in range(num_tasks)] ) <= total_size_max ) # 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) # 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 <vector> #include "absl/base/log_severity.h" #include "absl/log/globals.h" #include "absl/strings/str_format.h" #include "ortools/base/init_google.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, 12, 68}}, {{35, 85, 55, 65, 48, 101, 70, 83}}, {{125, 95, 90, 105, 59, 120, 36, 73}}, {{45, 110, 95, 115, 104, 83, 37, 71}}, {{60, 105, 80, 75, 59, 62, 93, 88}}, {{45, 65, 110, 95, 47, 31, 81, 34}}, {{38, 51, 107, 41, 69, 99, 115, 48}}, {{47, 85, 57, 71, 92, 77, 109, 36}}, {{39, 63, 97, 49, 118, 56, 92, 61}}, {{47, 101, 71, 60, 88, 109, 52, 90}}, }}; 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); const std::vector<int64_t> task_sizes = {{10, 7, 3, 12, 15, 4, 11, 5}}; // Maximum total of task sizes for any worker const int total_size_max = 15; // 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 += LinearExpr(x[worker][task]) * task_sizes[task]; } solver->MakeRowConstraint(worker_sum <= total_size_max); } // 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); } // 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[]) { InitGoogle(argv[0], &argc, &argv, true); absl::SetStderrThreshold(absl::LogSeverityAtLeast::kInfo); 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 AssignmentTaskSizesMip { public static void main(String[] args) { Loader.loadNativeLibraries(); // Data double[][] costs = { {90, 76, 75, 70, 50, 74, 12, 68}, {35, 85, 55, 65, 48, 101, 70, 83}, {125, 95, 90, 105, 59, 120, 36, 73}, {45, 110, 95, 115, 104, 83, 37, 71}, {60, 105, 80, 75, 59, 62, 93, 88}, {45, 65, 110, 95, 47, 31, 81, 34}, {38, 51, 107, 41, 69, 99, 115, 48}, {47, 85, 57, 71, 92, 77, 109, 36}, {39, 63, 97, 49, 118, 56, 92, 61}, {47, 101, 71, 60, 88, 109, 52, 90}, }; 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(); final int[] taskSizes = {10, 7, 3, 12, 15, 4, 11, 5}; // Maximum total of task sizes for any worker final int totalSizeMax = 15; // 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 max task size. for (int worker : allWorkers) { MPConstraint constraint = solver.makeConstraint(0, totalSizeMax, ""); for (int task : allTasks) { constraint.setCoefficient(x[worker][task], taskSizes[task]); } } // 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); } } // 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 AssignmentTaskSizesMip() {} }
C#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver; public class AssignmentTaskSizesMip { static void Main() { // Data. int[,] costs = { { 90, 76, 75, 70, 50, 74, 12, 68 }, { 35, 85, 55, 65, 48, 101, 70, 83 }, { 125, 95, 90, 105, 59, 120, 36, 73 }, { 45, 110, 95, 115, 104, 83, 37, 71 }, { 60, 105, 80, 75, 59, 62, 93, 88 }, { 45, 65, 110, 95, 47, 31, 81, 34 }, { 38, 51, 107, 41, 69, 99, 115, 48 }, { 47, 85, 57, 71, 92, 77, 109, 36 }, { 39, 63, 97, 49, 118, 56, 92, 61 }, { 47, 101, 71, 60, 88, 109, 52, 90 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); int[] allWorkers = Enumerable.Range(0, numWorkers).ToArray(); int[] allTasks = Enumerable.Range(0, numTasks).ToArray(); int[] taskSizes = { 10, 7, 3, 12, 15, 4, 11, 5 }; // Maximum total of task sizes for any worker int totalSizeMax = 15; // 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 max task size. foreach (int worker in allWorkers) { Constraint constraint = solver.MakeConstraint(0, totalSizeMax, ""); foreach (int task in allTasks) { constraint.SetCoefficient(x[worker, task], taskSizes[task]); } } // 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); } } // 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."); } } }