La sezione precedente mostrava come trovare tutte le soluzioni a un problema di CP. Ora ti mostreremo come trovare una soluzione ottimale. Ad esempio, risolveremo il seguente problema di ottimizzazione.
- Massimizza 2x + 2y + 3z rispettando i seguenti vincoli:
-
x + 7⁄2 Y + 3⁄2 z ≤ 25 3x - 5y + 7z ≤ 45 5x + 2y - 6z ≤ 37 x, y, z ≥ 0 x, y, z numeri interi
Per aumentare la velocità di calcolo, il risolutore CP-SAT lavora sui numeri interi. Ciò significa che tutti i vincoli e l'obiettivo devono avere coefficienti interi. Nell'esempio precedente, il primo vincolo non soddisfa questa condizione. Per risolvere il problema, devi prima trasformare il vincolo moltiplicandolo per un numero intero sufficientemente grande da convertire tutti i coefficienti in numeri interi. Questa operazione viene mostrata nella sezione Vincoli di seguito.
Soluzione che utilizza il risolutore CP-SAT
Le seguenti sezioni presentano un programma Python che risolve il problema utilizzando il risolutore CP-SAT.
Importa le librerie
Il seguente codice importa la libreria richiesta.
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;
Dichiara il modello
Il codice seguente dichiara il modello per il problema.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Crea le variabili
Il codice seguente crea le variabili per il 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");
Definisci i vincoli
Dal primo vincolo,
x + 7⁄2 Y + 3⁄2 z | ≤ | 25 |
ha coefficienti non interi, devi prima moltiplicare l'intero vincolo per un numero intero sufficientemente grande per convertire i coefficienti in numeri interi. In questo caso, puoi moltiplicare per 2 e generare il nuovo vincolo
2x + 7y + 3z | ≤ | 50 |
Questo non modifica il problema, poiché il vincolo originale ha esattamente le stesse soluzioni del vincolo trasformato.
Il codice seguente definisce i tre vincoli lineari per il 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);
Definire la funzione obiettivo
Il codice seguente definisce la funzione dell'obiettivo per il problema e lo dichiara un problema di massimizzazione:
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);
Chiama il risolutore
Il codice seguente chiama il risolutore.
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);
Visualizza la soluzione
Il codice seguente visualizza i risultati.
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."); }
L'output è mostrato di seguito:
Maximum of objective function: 35 x value: 7 y value: 3 z value: 5
L'intero programma
L'intero programma è illustrato di seguito.
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"); } }