En la sección anterior, se mostró cómo encontrar todas las soluciones a un problema de CP. A continuación, te mostraremos cómo encontrar una solución óptima. Como ejemplo, resolveremos el siguiente problema de optimización.
- Maximizar 2x + 2y + 3z sujeto a las siguientes restricciones:
-
x + 7⁄2 y + 3⁄2 z ≤ 25 3x - 5y + 7z ≤ 45 5x + 2y - 6z ≤ 37 x, y y z ≥ 0 x, y, z números enteros
Para aumentar la velocidad de procesamiento, el solucionador de problemas CP-SAT funciona con números enteros. Esto significa que todas las restricciones y el objetivo deben tener coeficientes de números enteros. En el ejemplo anterior, la primera restricción no cumple con esta condición. Para resolver el problema, primero debes transformar la restricción multiplicándola por un número entero lo suficientemente grande como para convertir todos los coeficientes en números enteros. Esto se muestra en la sección Restricciones a continuación.
Solución con el solucionador de problemas CP-SAT
En las siguientes secciones, se presenta un programa de Python que resuelve el problema con el solucionador de problemas CP-SAT.
Importa las bibliotecas
Con el siguiente código, se importa la biblioteca requerida.
Python
from ortools.sat.python import cp_model
C++
#include <stdint.h> #include <stdlib.h> #include <algorithm> #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" #include "ortools/util/sorted_interval_list.h"
Java
import static java.util.Arrays.stream; 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;
C#
using System; using System.Linq; using Google.OrTools.Sat;
Declara el modelo
El siguiente código declara el modelo para el problema.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Crea las variables
El siguiente código crea las variables para el problema.
Python
var_upper_bound = max(50, 45, 37) x = model.new_int_var(0, var_upper_bound, "x") y = model.new_int_var(0, var_upper_bound, "y") z = model.new_int_var(0, var_upper_bound, "z")
C++
int64_t var_upper_bound = std::max({50, 45, 37}); const Domain domain(0, var_upper_bound); const IntVar x = cp_model.NewIntVar(domain).WithName("x"); const IntVar y = cp_model.NewIntVar(domain).WithName("y"); const IntVar z = cp_model.NewIntVar(domain).WithName("z");
Java
int varUpperBound = stream(new int[] {50, 45, 37}).max().getAsInt(); IntVar x = model.newIntVar(0, varUpperBound, "x"); IntVar y = model.newIntVar(0, varUpperBound, "y"); IntVar z = model.newIntVar(0, varUpperBound, "z");
C#
int varUpperBound = new int[] { 50, 45, 37 }.Max(); IntVar x = model.NewIntVar(0, varUpperBound, "x"); IntVar y = model.NewIntVar(0, varUpperBound, "y"); IntVar z = model.NewIntVar(0, varUpperBound, "z");
Define las restricciones
Desde la primera limitación,
x + 7⁄2 y + 3⁄2 z | ≤ | 25 |
tiene coeficientes que no son números enteros, primero debes multiplicar toda la restricción por un número entero lo suficientemente grande para convertir los coeficientes en números enteros. En este caso, puedes multiplicar por 2, lo que da como resultado la nueva restricción.
2x + 7y + 3z | ≤ | 50 |
Esto no cambia el problema, ya que la restricción original tiene exactamente las mismas soluciones que la restricción transformada.
El siguiente código define las tres restricciones lineales para el problema:
Python
model.add(2 * x + 7 * y + 3 * z <= 50) model.add(3 * x - 5 * y + 7 * z <= 45) model.add(5 * x + 2 * y - 6 * z <= 37)
C++
cp_model.AddLessOrEqual(2 * x + 7 * y + 3 * z, 50); cp_model.AddLessOrEqual(3 * x - 5 * y + 7 * z, 45); cp_model.AddLessOrEqual(5 * x + 2 * y - 6 * z, 37);
Java
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 7, 3}), 50); model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {3, -5, 7}), 45); model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {5, 2, -6}), 37);
C#
model.Add(2 * x + 7 * y + 3 * z <= 50); model.Add(3 * x - 5 * y + 7 * z <= 45); model.Add(5 * x + 2 * y - 6 * z <= 37);
Define la función objetivo
El siguiente código define la función objetiva del problema y declara que es un problema de maximización:
Python
model.maximize(2 * x + 2 * y + 3 * z)
C++
cp_model.Maximize(2 * x + 2 * y + 3 * z);
Java
model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3}));
C#
model.Maximize(2 * x + 2 * y + 3 * z);
Cómo llamar al solucionador
El siguiente código llama al solucionador.
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);
Muestra la solución
Los resultados se muestran con el siguiente código.
Python
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print(f"Maximum of objective function: {solver.objective_value}\n") print(f"x = {solver.value(x)}") print(f"y = {solver.value(y)}") print(f"z = {solver.value(z)}") else: print("No solution found.")
C++
if (response.status() == CpSolverStatus::OPTIMAL || response.status() == CpSolverStatus::FEASIBLE) { // Get the value of x in the solution. LOG(INFO) << "Maximum of objective function: " << response.objective_value(); LOG(INFO) << "x = " << SolutionIntegerValue(response, x); LOG(INFO) << "y = " << SolutionIntegerValue(response, y); LOG(INFO) << "z = " << SolutionIntegerValue(response, z); } else { LOG(INFO) << "No solution found."; }
Java
if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { System.out.printf("Maximum of objective function: %f%n", solver.objectiveValue()); System.out.println("x = " + solver.value(x)); System.out.println("y = " + solver.value(y)); System.out.println("z = " + solver.value(z)); } else { System.out.println("No solution found."); }
C#
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine($"Maximum of objective function: {solver.ObjectiveValue}"); Console.WriteLine("x = " + solver.Value(x)); Console.WriteLine("y = " + solver.Value(y)); Console.WriteLine("z = " + solver.Value(z)); } else { Console.WriteLine("No solution found."); }
El resultado se muestra a continuación:
Maximum of objective function: 35 x value: 7 y value: 3 z value: 5
Todo el programa
A continuación, se muestra todo el programa.
Python
"""Simple solve.""" from ortools.sat.python import cp_model def main() -> None: """Minimal CP-SAT example to showcase calling the solver.""" # Creates the model. model = cp_model.CpModel() # Creates the variables. var_upper_bound = max(50, 45, 37) x = model.new_int_var(0, var_upper_bound, "x") y = model.new_int_var(0, var_upper_bound, "y") z = model.new_int_var(0, var_upper_bound, "z") # Creates the constraints. model.add(2 * x + 7 * y + 3 * z <= 50) model.add(3 * x - 5 * y + 7 * z <= 45) model.add(5 * x + 2 * y - 6 * z <= 37) model.maximize(2 * x + 2 * y + 3 * z) # Creates a solver and solves the model. solver = cp_model.CpSolver() status = solver.solve(model) if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print(f"Maximum of objective function: {solver.objective_value}\n") print(f"x = {solver.value(x)}") print(f"y = {solver.value(y)}") print(f"z = {solver.value(z)}") else: print("No solution found.") # Statistics. print("\nStatistics") print(f" status : {solver.status_name(status)}") print(f" conflicts: {solver.num_conflicts}") print(f" branches : {solver.num_branches}") print(f" wall time: {solver.wall_time} s") if __name__ == "__main__": main()
C++
#include <stdint.h> #include <stdlib.h> #include <algorithm> #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" #include "ortools/util/sorted_interval_list.h" namespace operations_research { namespace sat { void CpSatExample() { CpModelBuilder cp_model; int64_t var_upper_bound = std::max({50, 45, 37}); const Domain domain(0, var_upper_bound); const IntVar x = cp_model.NewIntVar(domain).WithName("x"); const IntVar y = cp_model.NewIntVar(domain).WithName("y"); const IntVar z = cp_model.NewIntVar(domain).WithName("z"); cp_model.AddLessOrEqual(2 * x + 7 * y + 3 * z, 50); cp_model.AddLessOrEqual(3 * x - 5 * y + 7 * z, 45); cp_model.AddLessOrEqual(5 * x + 2 * y - 6 * z, 37); cp_model.Maximize(2 * x + 2 * y + 3 * z); // Solving part. const CpSolverResponse response = Solve(cp_model.Build()); if (response.status() == CpSolverStatus::OPTIMAL || response.status() == CpSolverStatus::FEASIBLE) { // Get the value of x in the solution. LOG(INFO) << "Maximum of objective function: " << response.objective_value(); LOG(INFO) << "x = " << SolutionIntegerValue(response, x); LOG(INFO) << "y = " << SolutionIntegerValue(response, y); LOG(INFO) << "z = " << SolutionIntegerValue(response, z); } else { LOG(INFO) << "No solution found."; } // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << CpSolverResponseStats(response); } } // namespace sat } // namespace operations_research int main() { operations_research::sat::CpSatExample(); return EXIT_SUCCESS; }
Java
package com.google.ortools.sat.samples; import static java.util.Arrays.stream; 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; /** Minimal CP-SAT example to showcase calling the solver. */ public final class CpSatExample { public static void main(String[] args) { Loader.loadNativeLibraries(); // Create the model. CpModel model = new CpModel(); // Create the variables. int varUpperBound = stream(new int[] {50, 45, 37}).max().getAsInt(); IntVar x = model.newIntVar(0, varUpperBound, "x"); IntVar y = model.newIntVar(0, varUpperBound, "y"); IntVar z = model.newIntVar(0, varUpperBound, "z"); // Create the constraints. model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 7, 3}), 50); model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {3, -5, 7}), 45); model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {5, 2, -6}), 37); model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3})); // Create a solver and solve the model. CpSolver solver = new CpSolver(); CpSolverStatus status = solver.solve(model); if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) { System.out.printf("Maximum of objective function: %f%n", solver.objectiveValue()); System.out.println("x = " + solver.value(x)); System.out.println("y = " + solver.value(y)); System.out.println("z = " + solver.value(z)); } else { System.out.println("No solution found."); } // Statistics. System.out.println("Statistics"); System.out.printf(" conflicts: %d%n", solver.numConflicts()); System.out.printf(" branches : %d%n", solver.numBranches()); System.out.printf(" wall time: %f s%n", solver.wallTime()); } private CpSatExample() {} }
C#
using System; using System.Linq; using Google.OrTools.Sat; public class CpSatExample { static void Main() { // Creates the model. CpModel model = new CpModel(); // Creates the variables. int varUpperBound = new int[] { 50, 45, 37 }.Max(); IntVar x = model.NewIntVar(0, varUpperBound, "x"); IntVar y = model.NewIntVar(0, varUpperBound, "y"); IntVar z = model.NewIntVar(0, varUpperBound, "z"); // Creates the constraints. model.Add(2 * x + 7 * y + 3 * z <= 50); model.Add(3 * x - 5 * y + 7 * z <= 45); model.Add(5 * x + 2 * y - 6 * z <= 37); model.Maximize(2 * x + 2 * y + 3 * z); // Creates a solver and solves the model. CpSolver solver = new CpSolver(); CpSolverStatus status = solver.Solve(model); if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible) { Console.WriteLine($"Maximum of objective function: {solver.ObjectiveValue}"); Console.WriteLine("x = " + solver.Value(x)); Console.WriteLine("y = " + solver.Value(y)); Console.WriteLine("z = " + solver.Value(z)); } 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"); } }