Im vorherigen Abschnitt wurde gezeigt, wie Sie alle Lösungen für ein CP-Problem finden. Als Nächstes zeigen wir, wie Sie eine optimale Lösung finden. Als Beispiel lösen wir das folgende Optimierungsproblem.
- Maximieren Sie 2x + 2y + 3z gemäß den folgenden Einschränkungen:
-
x + 7⁄2 y + 3⁄2 z ≤ 25 3x–5y + 7z ≤ 45 5x + 2y – 6z ≤ 37 x, y, z ≥ 0 x-, y- und z-Ganzzahlen
Der CP-SAT-Beheber arbeitet mit den Ganzzahlen, um die Rechengeschwindigkeit zu erhöhen. Das bedeutet, dass alle Einschränkungen und das Ziel ganzzahlige Koeffizienten haben müssen. Im obigen Beispiel erfüllt die erste Einschränkung diese Bedingung nicht. Zur Lösung des Problems müssen Sie zuerst die Einschränkung transformieren. Multiplizieren Sie sie dazu mit einer ausreichend großen Ganzzahl, um alle Koeffizienten in Ganzzahlen umzuwandeln. Dies wird im Abschnitt Einschränkungen unten gezeigt.
Lösung, die den CP-SAT-Beheber verwendet
In den folgenden Abschnitten wird ein Python-Programm vorgestellt, das das Problem mit dem CP-SAT-Resolver löst.
Bibliotheken importieren
Mit dem folgenden Code wird die erforderliche Bibliothek importiert.
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;
Modell deklarieren
Mit dem folgenden Code wird das Modell für das Problem deklariert.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Variablen erstellen
Mit dem folgenden Code werden die Variablen für das Problem erstellt.
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");
Einschränkungen definieren
Seit der ersten Einschränkung
x + 7⁄2 y + 3⁄2 z | ≤ | 25 |
Nicht-Ganzzahlkoeffizienten enthält, müssen Sie zuerst die gesamte Einschränkung mit einer ausreichend großen Ganzzahl multiplizieren, um die Koeffizienten in Ganzzahlen umzuwandeln. In diesem Fall können Sie sie mit 2 multiplizieren, was zur neuen Einschränkung führt.
2x + 7y + 3z | ≤ | 50 |
Dies ändert das Problem nicht, da die ursprüngliche Einschränkung genau die gleichen Lösungen wie die transformierte Einschränkung bietet.
Der folgende Code definiert die drei linearen Einschränkungen für das Problem:
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);
Die Zielfunktion definieren
Mit dem folgenden Code wird die Zielfunktion für das Problem definiert und als Maximierungsproblem deklariert:
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);
Matherechner aufrufen
Mit dem folgenden Code wird der Solver aufgerufen.
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);
Lösung anzeigen
Mit dem folgenden Code werden die Ergebnisse angezeigt.
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."); }
Die Ausgabe sieht so aus:
Maximum of objective function: 35 x value: 7 y value: 3 z value: 5
Das gesamte Programm
Das gesamte Programm ist unten zu sehen.
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"); } }