W poprzedniej sekcji pokazaliśmy, jak znaleźć wszystkie rozwiązania problemu CP. Teraz pokażemy, jak znaleźć optymalne rozwiązanie. Rozwiążemy na przykład ten problem z optymalizacją.
- Maksymalizuj wymiary 2x + 2y + 3z z zastrzeżeniem tych ograniczeń:
-
x + 7⁄2 y + 3⁄2 z ≤ 25 3x – 5y + 7z ≤ 45 5x + 2y - 6z ≤ 37 x, y, z ≥ 0 liczby całkowite x, y, z
Aby zwiększyć szybkość obliczeniową, rozwiązanie CP-SAT wykorzystuje liczby całkowite. Oznacza to, że wszystkie ograniczenia i cel muszą mieć współczynniki całkowite. W przykładzie powyżej pierwsze ograniczenie nie spełnia tego warunku. Aby rozwiązać ten problem, musisz najpierw przekształcić ograniczenie, mnożąc je przez wystarczająco dużą liczbę całkowitą, aby przekonwertować wszystkie współczynniki na liczby całkowite. Informacje o tym znajdziesz w sekcji Ograniczenia poniżej.
Rozwiązanie korzystające z rozwiązania CP-SAT
W kolejnych sekcjach przedstawiamy program w Pythonie, który rozwiązuje problem przy użyciu rozwiązania CP-SAT.
Zaimportuj biblioteki
Poniższy kod importuje wymaganą bibliotekę.
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;
Deklarowanie modelu
Poniższy kod deklaruje model problemu.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Tworzenie zmiennych
Poniższy kod tworzy zmienne odpowiadające za problem.
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");
Zdefiniuj ograniczenia
Od pierwszego ograniczenia
x + 7⁄2 y + 3⁄2 z | ≤ | 25 |
ma współczynniki niecałkowite, musisz najpierw pomnożyć całe ograniczenie przez wystarczająco dużą liczbę całkowitą, aby przekonwertować współczynniki na liczby całkowite. W tym przypadku możesz mnożyć wynik przez 2, co daje nowe ograniczenie
2x + 7y + 3z | ≤ | 50 |
Nie zmienia to problemu, ponieważ pierwotne ograniczenie ma dokładnie te same rozwiązania co ograniczenie przekształcone.
W tym kodzie zdefiniowano 3 ograniczenia liniowe występujące w problemie:
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);
Zdefiniuj funkcję celu
Ten kod określa cel zadania i określa, że jest to problem maksymalizacji:
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);
Wywoływanie rozwiązania
Ten kod wywołuje funkcję rozwiązania.
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);
Wyświetl rozwiązanie
Poniższy kod pozwala wyświetlić wyniki.
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."); }
Dane wyjściowe są widoczne poniżej:
Maximum of objective function: 35 x value: 7 y value: 3 z value: 5
Cały program
Cały program jest widoczny poniżej.
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"); } }