En esta sección, se presenta un ejemplo que muestra cómo resolver un problema de asignación con el solucionador MIP y el solucionador CP-SAT.
Ejemplo
En el ejemplo hay cinco trabajadores (números del 0 al 4) y cuatro tareas (numeradas) 0-3). Ten en cuenta que hay un trabajador más que en el ejemplo de la Descripción general.
Los costos de asignar trabajadores a las tareas se muestran en el siguiente tabla.
| Trabajador | Tarea 0 | Tarea 1 | Tarea 2 | Tarea 3 |
|---|---|---|---|---|
| 0 | 90 | 80 | 75 | 70 |
| 1 | 35 | 85 | 55 | 65 |
| 2 | 125 | 95 | 90 | 95 |
| 3 | 45 | 110 | 95 | 115 |
| 4 | 50 | 100 | 90 | 100 |
El problema es asignar a cada trabajador, al menos, una tarea, sin que dos trabajadores realicen la misma tarea y, al mismo tiempo, minimizar el costo total. Como hay más trabajadores que tareas, a un trabajador no se le asignará una tarea.
Solución MIP
En las siguientes secciones, se describe cómo resolver el problema usando la Wrapper de MPSolver:
Importa las bibliotecas
El siguiente código importa las bibliotecas necesarias.
Python
from ortools.linear_solver import pywraplp
C++
#include <memory> #include <vector> #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;
C#
using System; using Google.OrTools.LinearSolver;
Crea los datos
Con el siguiente código, se crean los datos para el problema.
Python
costs = [
[90, 80, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 95],
[45, 110, 95, 115],
[50, 100, 90, 100],
]
num_workers = len(costs)
num_tasks = len(costs[0])C++
const std::vector<std::vector<double>> costs{ {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; const int num_workers = costs.size(); const int num_tasks = costs[0].size();
Java
double[][] costs = {
{90, 80, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 95},
{45, 110, 95, 115},
{50, 100, 90, 100},
};
int numWorkers = costs.length;
int numTasks = costs[0].length;C#
int[,] costs = {
{ 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);El array costs corresponde a la tabla de costos.
para asignar trabajadores a las tareas, como se muestra arriba.
Cómo declarar el solucionador de MIP
El siguiente código declara el solucionador de MIP.
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; }
Crea las variables
Con el siguiente código, se crean variables de números enteros binarios para el problema.
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 i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, "")
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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { x[i][j] = solver->MakeIntVar(0, 1, ""); } }
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 i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { x[i][j] = solver.makeIntVar(0, 1, ""); } }
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]; for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}"); } }
Crea las restricciones
El siguiente código crea las restricciones para el problema.
Python
# Each worker is assigned to at most 1 task. for i in range(num_workers): solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1) # Each task is assigned to exactly one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)
C++
// Each worker is assigned to at most one task. for (int i = 0; i < num_workers; ++i) { LinearExpr worker_sum; for (int j = 0; j < num_tasks; ++j) { worker_sum += x[i][j]; } solver->MakeRowConstraint(worker_sum <= 1.0); } // Each task is assigned to exactly one worker. for (int j = 0; j < num_tasks; ++j) { LinearExpr task_sum; for (int i = 0; i < num_workers; ++i) { task_sum += x[i][j]; } solver->MakeRowConstraint(task_sum == 1.0); }
Java
// Each worker is assigned to at most one task. for (int i = 0; i < numWorkers; ++i) { MPConstraint constraint = solver.makeConstraint(0, 1, ""); for (int j = 0; j < numTasks; ++j) { constraint.setCoefficient(x[i][j], 1); } } // Each task is assigned to exactly one worker. for (int j = 0; j < numTasks; ++j) { MPConstraint constraint = solver.makeConstraint(1, 1, ""); for (int i = 0; i < numWorkers; ++i) { constraint.setCoefficient(x[i][j], 1); } }
C#
// Each worker is assigned to at most one task. for (int i = 0; i < numWorkers; ++i) { Constraint constraint = solver.MakeConstraint(0, 1, ""); for (int j = 0; j < numTasks; ++j) { constraint.SetCoefficient(x[i, j], 1); } } // Each task is assigned to exactly one worker. for (int j = 0; j < numTasks; ++j) { Constraint constraint = solver.MakeConstraint(1, 1, ""); for (int i = 0; i < numWorkers; ++i) { constraint.SetCoefficient(x[i, j], 1); } }
Crea la función objetiva
Con el siguiente código, se crea la función objetiva para el problema.
Python
objective_terms = [] for i in range(num_workers): for j in range(num_tasks): objective_terms.append(costs[i][j] * x[i, j]) solver.Minimize(solver.Sum(objective_terms))
C++
MPObjective* const objective = solver->MutableObjective(); for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { objective->SetCoefficient(x[i][j], costs[i][j]); } } objective->SetMinimization();
Java
MPObjective objective = solver.objective(); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { objective.setCoefficient(x[i][j], costs[i][j]); } } objective.setMinimization();
C#
Objective objective = solver.Objective(); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { objective.SetCoefficient(x[i, j], costs[i, j]); } } objective.SetMinimization();
El valor de la función objetivo es el costo total de todas las variables a las que se les asigna valor 1 por el solucionador.
Invocar el solucionador
El siguiente código invoca la herramienta de resolución.
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();
Imprimir la solución
El siguiente código imprime la solución al problema.
Python
if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE: print(f"Total cost = {solver.Objective().Value()}\n") for i in range(num_workers): for j in range(num_tasks): # Test if x[i,j] is 1 (with tolerance for floating point arithmetic). if x[i, j].solution_value() > 0.5: print(f"Worker {i} assigned to task {j}." + f" Cost: {costs[i][j]}") 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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[i][j]->solution_value() > 0.5) { LOG(INFO) << "Worker " << i << " assigned to task " << j << ". Cost = " << costs[i][j]; } } }
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 i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[i][j].solutionValue() > 0.5) { System.out.println( "Worker " + i + " assigned to task " + j + ". Cost = " + costs[i][j]); } } } } 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"); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { // Test if x[i, j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[i, j].SolutionValue() > 0.5) { Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}"); } } } } else { Console.WriteLine("No solution found."); }
Este es el resultado del programa.
Total cost = 265.0 Worker 0 assigned to task 3. Cost = 70 Worker 1 assigned to task 2. Cost = 55 Worker 2 assigned to task 1. Cost = 95 Worker 3 assigned to task 0. Cost = 45
Completar programas
Estos son los programas completos de la solución del MIP.
Python
from ortools.linear_solver import pywraplp def main(): # Data costs = [ [90, 80, 75, 70], [35, 85, 55, 65], [125, 95, 90, 95], [45, 110, 95, 115], [50, 100, 90, 100], ] num_workers = len(costs) num_tasks = len(costs[0]) # 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 i in range(num_workers): for j in range(num_tasks): x[i, j] = solver.IntVar(0, 1, "") # Constraints # Each worker is assigned to at most 1 task. for i in range(num_workers): solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1) # Each task is assigned to exactly one worker. for j in range(num_tasks): solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1) # Objective objective_terms = [] for i in range(num_workers): for j in range(num_tasks): objective_terms.append(costs[i][j] * x[i, j]) 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 i in range(num_workers): for j in range(num_tasks): # Test if x[i,j] is 1 (with tolerance for floating point arithmetic). if x[i, j].solution_value() > 0.5: print(f"Worker {i} assigned to task {j}." + f" Cost: {costs[i][j]}") else: print("No solution found.") if __name__ == "__main__": main()
C++
#include <memory> #include <vector> #include "ortools/base/logging.h" #include "ortools/linear_solver/linear_solver.h" namespace operations_research { void AssignmentMip() { // Data const std::vector<std::vector<double>> costs{ {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; const int num_workers = costs.size(); const int num_tasks = costs[0].size(); // 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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { x[i][j] = solver->MakeIntVar(0, 1, ""); } } // Constraints // Each worker is assigned to at most one task. for (int i = 0; i < num_workers; ++i) { LinearExpr worker_sum; for (int j = 0; j < num_tasks; ++j) { worker_sum += x[i][j]; } solver->MakeRowConstraint(worker_sum <= 1.0); } // Each task is assigned to exactly one worker. for (int j = 0; j < num_tasks; ++j) { LinearExpr task_sum; for (int i = 0; i < num_workers; ++i) { task_sum += x[i][j]; } solver->MakeRowConstraint(task_sum == 1.0); } // Objective. MPObjective* const objective = solver->MutableObjective(); for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { objective->SetCoefficient(x[i][j], costs[i][j]); } } 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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[i][j]->solution_value() > 0.5) { LOG(INFO) << "Worker " << i << " assigned to task " << j << ". Cost = " << costs[i][j]; } } } } } // namespace operations_research int main(int argc, char** argv) { operations_research::AssignmentMip(); 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; /** MIP example that solves an assignment problem. */ public class AssignmentMip { public static void main(String[] args) { Loader.loadNativeLibraries(); // Data double[][] costs = { {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; int numWorkers = costs.length; int numTasks = costs[0].length; // 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 i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { x[i][j] = solver.makeIntVar(0, 1, ""); } } // Constraints // Each worker is assigned to at most one task. for (int i = 0; i < numWorkers; ++i) { MPConstraint constraint = solver.makeConstraint(0, 1, ""); for (int j = 0; j < numTasks; ++j) { constraint.setCoefficient(x[i][j], 1); } } // Each task is assigned to exactly one worker. for (int j = 0; j < numTasks; ++j) { MPConstraint constraint = solver.makeConstraint(1, 1, ""); for (int i = 0; i < numWorkers; ++i) { constraint.setCoefficient(x[i][j], 1); } } // Objective MPObjective objective = solver.objective(); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { objective.setCoefficient(x[i][j], costs[i][j]); } } 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 i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { // Test if x[i][j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[i][j].solutionValue() > 0.5) { System.out.println( "Worker " + i + " assigned to task " + j + ". Cost = " + costs[i][j]); } } } } else { System.err.println("No solution found."); } } private AssignmentMip() {} }
C#
using System; using Google.OrTools.LinearSolver; public class AssignmentMip { static void Main() { // Data. int[,] costs = { { 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); // 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]; for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}"); } } // Constraints // Each worker is assigned to at most one task. for (int i = 0; i < numWorkers; ++i) { Constraint constraint = solver.MakeConstraint(0, 1, ""); for (int j = 0; j < numTasks; ++j) { constraint.SetCoefficient(x[i, j], 1); } } // Each task is assigned to exactly one worker. for (int j = 0; j < numTasks; ++j) { Constraint constraint = solver.MakeConstraint(1, 1, ""); for (int i = 0; i < numWorkers; ++i) { constraint.SetCoefficient(x[i, j], 1); } } // Objective Objective objective = solver.Objective(); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { objective.SetCoefficient(x[i, j], costs[i, j]); } } 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"); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { // Test if x[i, j] is 0 or 1 (with tolerance for floating point // arithmetic). if (x[i, j].SolutionValue() > 0.5) { Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}"); } } } } else { Console.WriteLine("No solution found."); } } }
Solución de SAT de CP
En las siguientes secciones, se describe cómo resolver el problema con el solucionador de problemas CP-SAT.
Importa las bibliotecas
El siguiente código importa las bibliotecas necesarias.
Python
import io import pandas as pd from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <vector> #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 Google.OrTools.Sat;
Declara el modelo
En el siguiente código, se declara el modelo CP-SAT.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Crea los datos
El siguiente código configura los datos para el problema.
Python
data_str = """
worker task cost
w1 t1 90
w1 t2 80
w1 t3 75
w1 t4 70
w2 t1 35
w2 t2 85
w2 t3 55
w2 t4 65
w3 t1 125
w3 t2 95
w3 t3 90
w3 t4 95
w4 t1 45
w4 t2 110
w4 t3 95
w4 t4 115
w5 t1 50
w5 t2 110
w5 t3 90
w5 t4 100
"""
data = pd.read_table(io.StringIO(data_str), sep=r"\s+")C++
const std::vector<std::vector<int>> costs{ {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; const int num_workers = static_cast<int>(costs.size()); const int num_tasks = static_cast<int>(costs[0].size());
Java
int[][] costs = {
{90, 80, 75, 70},
{35, 85, 55, 65},
{125, 95, 90, 95},
{45, 110, 95, 115},
{50, 100, 90, 100},
};
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, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 },
};
int numWorkers = costs.GetLength(0);
int numTasks = costs.GetLength(1);El array costs corresponde a la tabla de costos.
para asignar trabajadores a las tareas, como se muestra arriba.
Crea las variables
Con el siguiente código, se crean variables de números enteros binarios para el problema.
Python
x = model.new_bool_var_series(name="x", index=data.index)
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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { x[i][j] = cp_model.NewBoolVar(); } }
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.
for (int worker = 0; worker < numWorkers; ++worker)
{
for (int task = 0; task < numTasks; ++task)
{
x[worker, task] = model.NewBoolVar($"worker_{worker}_task_{task}");
}
}Crea las restricciones
El siguiente código crea las restricciones para el problema.
Python
# Each worker is assigned to at most one task. for unused_name, tasks in data.groupby("worker"): model.add_at_most_one(x[tasks.index]) # Each task is assigned to exactly one worker. for unused_name, workers in data.groupby("task"): model.add_exactly_one(x[workers.index])
C++
// Each worker is assigned to at most one task. for (int i = 0; i < num_workers; ++i) { cp_model.AddAtMostOne(x[i]); } // Each task is assigned to exactly one worker. for (int j = 0; j < num_tasks; ++j) { std::vector<BoolVar> tasks; for (int i = 0; i < num_workers; ++i) { tasks.push_back(x[i][j]); } 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. for (int worker = 0; worker < numWorkers; ++worker) { List<ILiteral> tasks = new List<ILiteral>(); for (int task = 0; task < numTasks; ++task) { tasks.Add(x[worker, task]); } model.AddAtMostOne(tasks); } // Each task is assigned to exactly one worker. for (int task = 0; task < numTasks; ++task) { List<ILiteral> workers = new List<ILiteral>(); for (int worker = 0; worker < numWorkers; ++worker) { workers.Add(x[worker, task]); } model.AddExactlyOne(workers); }
Crea la función objetiva
Con el siguiente código, se crea la función objetiva para el problema.
Python
model.minimize(data.cost.dot(x))
C++
LinearExpr total_cost; for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { total_cost += x[i][j] * costs[i][j]; } } 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(); for (int worker = 0; worker < numWorkers; ++worker) { for (int task = 0; task < numTasks; ++task) { obj.AddTerm((IntVar)x[worker, task], costs[worker, task]); } } model.Minimize(obj);
El valor de la función objetivo es el costo total de todas las variables a las que se les asigna valor 1 por el solucionador.
Invocar el solucionador
El siguiente código invoca la herramienta de resolución.
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}");
Imprimir la solución
El siguiente código imprime la solución al problema.
Python
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print(f"Total cost = {solver.objective_value}\n") selected = data.loc[solver.boolean_values(x).loc[lambda x: x].index] for unused_index, row in selected.iterrows(): print(f"{row.task} assigned to {row.worker} with a cost of {row.cost}") elif status == cp_model.INFEASIBLE: print("No solution found") else: print("Something is wrong, check the status and the log of the solve")
C++
if (response.status() == CpSolverStatus::INFEASIBLE) { LOG(FATAL) << "No solution found."; } LOG(INFO) << "Total cost: " << response.objective_value(); LOG(INFO); for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { if (SolutionBooleanValue(response, x[i][j])) { LOG(INFO) << "Task " << i << " assigned to worker " << j << ". Cost: " << costs[i][j]; } } }
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 i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { if (solver.booleanValue(x[i][j])) { System.out.println( "Worker " + i + " assigned to task " + j + ". Cost: " + costs[i][j]); } } } } 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"); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { if (solver.Value(x[i, j]) > 0.5) { Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}"); } } } } else { Console.WriteLine("No solution found."); }
Este es el resultado del programa.
Total cost = 265 Worker 0 assigned to task 3 Cost = 70 Worker 1 assigned to task 2 Cost = 55 Worker 2 assigned to task 1 Cost = 95 Worker 3 assigned to task 0 Cost = 45
Completar programas
Estos son los programas completos para la solución CP-SAT.
Python
import io import pandas as pd from ortools.sat.python import cp_model def main() -> None: # Data data_str = """ worker task cost w1 t1 90 w1 t2 80 w1 t3 75 w1 t4 70 w2 t1 35 w2 t2 85 w2 t3 55 w2 t4 65 w3 t1 125 w3 t2 95 w3 t3 90 w3 t4 95 w4 t1 45 w4 t2 110 w4 t3 95 w4 t4 115 w5 t1 50 w5 t2 110 w5 t3 90 w5 t4 100 """ data = pd.read_table(io.StringIO(data_str), sep=r"\s+") # Model model = cp_model.CpModel() # Variables x = model.new_bool_var_series(name="x", index=data.index) # Constraints # Each worker is assigned to at most one task. for unused_name, tasks in data.groupby("worker"): model.add_at_most_one(x[tasks.index]) # Each task is assigned to exactly one worker. for unused_name, workers in data.groupby("task"): model.add_exactly_one(x[workers.index]) # Objective model.minimize(data.cost.dot(x)) # 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") selected = data.loc[solver.boolean_values(x).loc[lambda x: x].index] for unused_index, row in selected.iterrows(): print(f"{row.task} assigned to {row.worker} with a cost of {row.cost}") elif status == cp_model.INFEASIBLE: print("No solution found") else: print("Something is wrong, check the status and the log of the solve") if __name__ == "__main__": main()
C++
#include <stdlib.h> #include <vector> #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 IntegerProgrammingExample() { // Data const std::vector<std::vector<int>> costs{ {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; const int num_workers = static_cast<int>(costs.size()); const int num_tasks = static_cast<int>(costs[0].size()); // 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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { x[i][j] = cp_model.NewBoolVar(); } } // Constraints // Each worker is assigned to at most one task. for (int i = 0; i < num_workers; ++i) { cp_model.AddAtMostOne(x[i]); } // Each task is assigned to exactly one worker. for (int j = 0; j < num_tasks; ++j) { std::vector<BoolVar> tasks; for (int i = 0; i < num_workers; ++i) { tasks.push_back(x[i][j]); } cp_model.AddExactlyOne(tasks); } // Objective LinearExpr total_cost; for (int i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { total_cost += x[i][j] * costs[i][j]; } } 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 i = 0; i < num_workers; ++i) { for (int j = 0; j < num_tasks; ++j) { if (SolutionBooleanValue(response, x[i][j])) { LOG(INFO) << "Task " << i << " assigned to worker " << j << ". Cost: " << costs[i][j]; } } } } } // namespace sat } // namespace operations_research int main(int argc, char** argv) { operations_research::sat::IntegerProgrammingExample(); return EXIT_SUCCESS; }
Java
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 AssignmentSat { public static void main(String[] args) { Loader.loadNativeLibraries(); // Data int[][] costs = { {90, 80, 75, 70}, {35, 85, 55, 65}, {125, 95, 90, 95}, {45, 110, 95, 115}, {50, 100, 90, 100}, }; 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(); // 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); } // 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 i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { if (solver.booleanValue(x[i][j])) { System.out.println( "Worker " + i + " assigned to task " + j + ". Cost: " + costs[i][j]); } } } } else { System.err.println("No solution found."); } } private AssignmentSat() {} }
C#
using System; using System.Collections.Generic; using Google.OrTools.Sat; public class AssignmentSat { public static void Main(String[] args) { // Data. int[,] costs = { { 90, 80, 75, 70 }, { 35, 85, 55, 65 }, { 125, 95, 90, 95 }, { 45, 110, 95, 115 }, { 50, 100, 90, 100 }, }; int numWorkers = costs.GetLength(0); int numTasks = costs.GetLength(1); // Model. CpModel model = new CpModel(); // Variables. BoolVar[,] x = new BoolVar[numWorkers, numTasks]; // Variables in a 1-dim array. for (int worker = 0; worker < numWorkers; ++worker) { for (int task = 0; task < numTasks; ++task) { x[worker, task] = model.NewBoolVar($"worker_{worker}_task_{task}"); } } // Constraints // Each worker is assigned to at most one task. for (int worker = 0; worker < numWorkers; ++worker) { List<ILiteral> tasks = new List<ILiteral>(); for (int task = 0; task < numTasks; ++task) { tasks.Add(x[worker, task]); } model.AddAtMostOne(tasks); } // Each task is assigned to exactly one worker. for (int task = 0; task < numTasks; ++task) { List<ILiteral> workers = new List<ILiteral>(); for (int worker = 0; worker < numWorkers; ++worker) { workers.Add(x[worker, task]); } model.AddExactlyOne(workers); } // Objective LinearExprBuilder obj = LinearExpr.NewBuilder(); for (int worker = 0; worker < numWorkers; ++worker) { for (int task = 0; task < numTasks; ++task) { obj.AddTerm((IntVar)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"); for (int i = 0; i < numWorkers; ++i) { for (int j = 0; j < numTasks; ++j) { if (solver.Value(x[i, j]) > 0.5) { Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}"); } } } } 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"); } }