В предыдущем разделе было показано, как найти все решения проблемы CP. Далее мы покажем, как найти оптимальное решение. В качестве примера мы решим следующую задачу оптимизации.
- Максимизируйте 2 x + 2 y + 3 z при соблюдении следующих ограничений:
х + 7 ⁄ 2 у + 3 ⁄ 2 z ≤ 25 3 х - 5 у + 7 з ≤ 45 5 х + 2 у - 6 з ≤ 37 х , у , я ≥ 0 x , y , z целые числа
Чтобы увеличить скорость вычислений, решатель CP-SAT работает с целыми числами. Это означает, что все ограничения и цель должны иметь целочисленные коэффициенты. В приведенном выше примере первое ограничение не соответствует этому условию. Чтобы решить проблему, необходимо сначала преобразовать ограничение, умножив его на достаточно большое целое число, чтобы преобразовать все коэффициенты в целые числа. Это показано в разделе «Ограничения» ниже.
Решение с использованием решателя CP-SAT
В следующих разделах представлена программа Python, которая решает задачу с помощью решателя CP-SAT.
Импортируйте библиотеки
Следующий код импортирует необходимую библиотеку.
from ortools.sat.python import cp_model
#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"
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;
using System;
using System.Linq;
using Google.OrTools.Sat;
Объявить модель
Следующий код объявляет модель проблемы.
model = cp_model.CpModel()
CpModelBuilder cp_model;
CpModel model = new CpModel();
CpModel model = new CpModel();
Создайте переменные
Следующий код создает переменные для проблемы.
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")
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");
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");
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");
Определите ограничения
Поскольку первое ограничение,
| х + 7 ⁄ 2 у + 3 ⁄ 2 z | ≤ | 25 |
имеет нецелые коэффициенты, необходимо сначала умножить все ограничение на достаточно большое целое число, чтобы преобразовать коэффициенты в целые числа. В этом случае вы можете умножить на 2, что приведет к новому ограничению
| 2 х + 7 у + 3 з | ≤ | 50 |
Это не меняет проблемы, поскольку исходное ограничение имеет точно такие же решения, что и преобразованное ограничение.
Следующий код определяет три линейных ограничения для задачи:
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)
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);
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.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)
cp_model.Maximize(2 * x + 2 * y + 3 * z);
model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3}));
model.Maximize(2 * x + 2 * y + 3 * z);
Вызов решателя
Следующий код вызывает решатель.
solver = cp_model.CpSolver()
status = solver.solve(model)
const CpSolverResponse response = Solve(cp_model.Build());
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);
CpSolver solver = new CpSolver();
CpSolverStatus 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.")
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.";
}
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.");
}
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.");
}
Результат показан ниже:
Maximum of objective function: 35 x value: 7 y value: 3 z value: 5
Вся программа
Вся программа показана ниже.
"""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()
#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;
}
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() {}
}
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");
}
}