В этом разделе описан исходный решатель программирования в ограничениях, который был заменен более совершенным решателем CP-SAT .
В следующих разделах описывается, как решить пример, описанный в разделе CP-SAT , на этот раз с использованием исходного решателя CP. Если вы настаиваете на использовании оригинального решателя CP, вы можете просмотреть справочник по API . Обратите внимание, что исходный решатель CP является основой библиотеки маршрутизации , и его API может потребоваться для настройки модели маршрутизации.
Импортируйте библиотеки
Следующий код импортирует необходимую библиотеку.
Питон
from ortools.constraint_solver import pywrapcp
С++
#include <ostream> #include <string> #include "ortools/constraint_solver/constraint_solver.h"
Ява
import com.google.ortools.Loader; import com.google.ortools.constraintsolver.DecisionBuilder; import com.google.ortools.constraintsolver.IntVar; import com.google.ortools.constraintsolver.Solver; import java.util.logging.Logger;
С#
using System; using Google.OrTools.ConstraintSolver;
Объявить решатель
Следующий код объявляет решатель.
Питон
solver = pywrapcp.Solver("CPSimple")
С++
Solver solver("CpSimple");
Ява
Solver solver = new Solver("CpSimple");
С#
Solver solver = new Solver("CpSimple");
Создайте переменные
Следующий код создает переменные для проблемы.
Решатель создает три переменные: x, y и z, каждая из которых может принимать значения 0, 1 или 2.
Питон
num_vals = 3 x = solver.IntVar(0, num_vals - 1, "x") y = solver.IntVar(0, num_vals - 1, "y") z = solver.IntVar(0, num_vals - 1, "z")
С++
const int64_t num_vals = 3; IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x"); IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y"); IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");
Ява
final long numVals = 3; final IntVar x = solver.makeIntVar(0, numVals - 1, "x"); final IntVar y = solver.makeIntVar(0, numVals - 1, "y"); final IntVar z = solver.makeIntVar(0, numVals - 1, "z");
С#
const long numVals = 3; IntVar x = solver.MakeIntVar(0, numVals - 1, "x"); IntVar y = solver.MakeIntVar(0, numVals - 1, "y"); IntVar z = solver.MakeIntVar(0, numVals - 1, "z");
Создайте ограничение
Следующий код создает ограничение x ≠ y
.
Питон
solver.Add(x != y) print("Number of constraints: ", solver.Constraints())
С++
solver.AddConstraint(solver.MakeAllDifferent({x, y})); LOG(INFO) << "Number of constraints: " << std::to_string(solver.constraints());
Ява
solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y})); logger.info("Number of constraints: " + solver.constraints());
С#
solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y })); Console.WriteLine($"Number of constraints: {solver.Constraints()}");
Вызов решателя
Следующий код вызывает решатель.
Построитель решений является основным источником исходных данных для исходного решателя CP. Он содержит следующее:
-
vars
— Массив, содержащий переменные для задачи. - Правило выбора следующей переменной, которой будет присвоено значение.
- Правило выбора следующего значения для присвоения этой переменной.
Подробности см. в разделе «Конструктор решений» .
Питон
decision_builder = solver.Phase( [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE )
С++
DecisionBuilder* const db = solver.MakePhase( {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
Ява
final DecisionBuilder db = solver.makePhase( new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
С#
DecisionBuilder db = solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
Распечатать решение
Код принтера решений, который отображает каждое решение по мере того, как его находит решатель, показан в следующем разделе.
Поскольку существует более одного решения нашей проблемы, можно перебирать решения с помощью цикла while solver.NextSolution()
. (Обратите внимание, что это работает иначе, чем принтер решения для решателя CP-SAT).
Питон
count = 0 solver.NewSearch(decision_builder) while solver.NextSolution(): count += 1 solution = f"Solution {count}:\n" for var in [x, y, z]: solution += f" {var.Name()} = {var.Value()}" print(solution) solver.EndSearch() print(f"Number of solutions found: {count}")
С++
int count = 0; solver.NewSearch(db); while (solver.NextSolution()) { ++count; LOG(INFO) << "Solution " << count << ":" << std::endl << " x=" << x->Value() << " y=" << y->Value() << " z=" << z->Value(); } solver.EndSearch(); LOG(INFO) << "Number of solutions found: " << solver.solutions();
Ява
int count = 0; solver.newSearch(db); while (solver.nextSolution()) { ++count; logger.info( String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value())); } solver.endSearch(); logger.info("Number of solutions found: " + solver.solutions());
С#
int count = 0; solver.NewSearch(db); while (solver.NextSolution()) { ++count; Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}"); } solver.EndSearch(); Console.WriteLine($"Number of solutions found: {solver.Solutions()}");
Результаты, возвращаемые решателем
Вот 18 решений, найденных решателем:
Number of constraints: 1 Solution 1: x = 0 y = 1 z = 0 Solution 2: x = 0 y = 1 z = 1 Solution 3: x = 0 y = 1 z = 2 Solution 4: x = 0 y = 2 z = 0 Solution 5: x = 0 y = 2 z = 1 Solution 6: x = 0 y = 2 z = 2 Solution 7: x = 1 y = 0 z = 0 Solution 8: x = 1 y = 0 z = 1 Solution 9: x = 1 y = 0 z = 2 Solution 10: x = 1 y = 2 z = 0 Solution 11: x = 1 y = 2 z = 1 Solution 12: x = 1 y = 2 z = 2 Solution 13: x = 2 y = 0 z = 0 Solution 14: x = 2 y = 0 z = 1 Solution 15: x = 2 y = 0 z = 2 Solution 16: x = 2 y = 1 z = 0 Solution 17: x = 2 y = 1 z = 1 Solution 18: x = 2 y = 1 z = 2 Number of solutions found: 18 Advanced usage: Problem solved in 2 ms Memory usage: 13918208 bytes
Полная программа
Вот полные программы для примера с использованием исходного решателя CP.
Питон
"""Simple Constraint optimization example.""" from ortools.constraint_solver import pywrapcp def main(): """Entry point of the program.""" # Instantiate the solver. solver = pywrapcp.Solver("CPSimple") # Create the variables. num_vals = 3 x = solver.IntVar(0, num_vals - 1, "x") y = solver.IntVar(0, num_vals - 1, "y") z = solver.IntVar(0, num_vals - 1, "z") # Constraint 0: x != y. solver.Add(x != y) print("Number of constraints: ", solver.Constraints()) # Solve the problem. decision_builder = solver.Phase( [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE ) # Print solution on console. count = 0 solver.NewSearch(decision_builder) while solver.NextSolution(): count += 1 solution = f"Solution {count}:\n" for var in [x, y, z]: solution += f" {var.Name()} = {var.Value()}" print(solution) solver.EndSearch() print(f"Number of solutions found: {count}") print("Advanced usage:") print(f"Problem solved in {solver.WallTime()}ms") print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes") if __name__ == "__main__": main()
С++
#include <ostream> #include <string> #include "ortools/constraint_solver/constraint_solver.h" namespace operations_research { void SimpleCpProgram() { // Instantiate the solver. Solver solver("CpSimple"); // Create the variables. const int64_t num_vals = 3; IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x"); IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y"); IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z"); // Constraint 0: x != y.. solver.AddConstraint(solver.MakeAllDifferent({x, y})); LOG(INFO) << "Number of constraints: " << std::to_string(solver.constraints()); // Solve the problem. DecisionBuilder* const db = solver.MakePhase( {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE); // Print solution on console. int count = 0; solver.NewSearch(db); while (solver.NextSolution()) { ++count; LOG(INFO) << "Solution " << count << ":" << std::endl << " x=" << x->Value() << " y=" << y->Value() << " z=" << z->Value(); } solver.EndSearch(); LOG(INFO) << "Number of solutions found: " << solver.solutions(); LOG(INFO) << "Advanced usage:" << std::endl << "Problem solved in " << std::to_string(solver.wall_time()) << "ms" << std::endl << "Memory usage: " << std::to_string(Solver::MemoryUsage()) << "bytes"; } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::SimpleCpProgram(); return EXIT_SUCCESS; }
Ява
package com.google.ortools.constraintsolver.samples; import com.google.ortools.Loader; import com.google.ortools.constraintsolver.DecisionBuilder; import com.google.ortools.constraintsolver.IntVar; import com.google.ortools.constraintsolver.Solver; import java.util.logging.Logger; /** Simple CP Program.*/ public class SimpleCpProgram { private SimpleCpProgram() {} private static final Logger logger = Logger.getLogger(SimpleCpProgram.class.getName()); public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate the solver. Solver solver = new Solver("CpSimple"); // Create the variables. final long numVals = 3; final IntVar x = solver.makeIntVar(0, numVals - 1, "x"); final IntVar y = solver.makeIntVar(0, numVals - 1, "y"); final IntVar z = solver.makeIntVar(0, numVals - 1, "z"); // Constraint 0: x != y.. solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y})); logger.info("Number of constraints: " + solver.constraints()); // Solve the problem. final DecisionBuilder db = solver.makePhase( new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); // Print solution on console. int count = 0; solver.newSearch(db); while (solver.nextSolution()) { ++count; logger.info( String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value())); } solver.endSearch(); logger.info("Number of solutions found: " + solver.solutions()); logger.info(String.format("Advanced usage:\nProblem solved in %d ms\nMemory usage: %d bytes", solver.wallTime(), Solver.memoryUsage())); } }
С#
using System; using Google.OrTools.ConstraintSolver; /// <summary> /// This is a simple CP program. /// </summary> public class SimpleCpProgram { public static void Main(String[] args) { // Instantiate the solver. Solver solver = new Solver("CpSimple"); // Create the variables. const long numVals = 3; IntVar x = solver.MakeIntVar(0, numVals - 1, "x"); IntVar y = solver.MakeIntVar(0, numVals - 1, "y"); IntVar z = solver.MakeIntVar(0, numVals - 1, "z"); // Constraint 0: x != y.. solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y })); Console.WriteLine($"Number of constraints: {solver.Constraints()}"); // Solve the problem. DecisionBuilder db = solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE); // Print solution on console. int count = 0; solver.NewSearch(db); while (solver.NextSolution()) { ++count; Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}"); } solver.EndSearch(); Console.WriteLine($"Number of solutions found: {solver.Solutions()}"); Console.WriteLine("Advanced usage:"); Console.WriteLine($"Problem solved in {solver.WallTime()}ms"); Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes"); } }
Конструктор решений
Основным входным сигналом для исходного решателя CP является построитель решений , который содержит переменные для задачи и устанавливает параметры для решателя.
Пример кода в предыдущем разделе создает построитель решений с использованием метода Phase
(соответствующего методу C++ MakePhase
.
Термин «Фаза» относится к этапу поиска. В этом простом примере имеется только одна фаза, но для более сложных задач построитель решений может иметь более одной фазы, так что решатель может использовать разные стратегии поиска от одной фазы к другой.
Phase
метод имеет три входных параметра:
-
vars
— Массив, содержащий переменные для задачи, в данном случае это[x, y, z]
. -
IntVarStrategy
— Правило выбора следующей несвязанной переменной, которой будет присвоено значение. Здесь код использует значение по умолчаниюCHOOSE_FIRST_UNBOUND
, что означает, что на каждом этапе решатель выбирает первую несвязанную переменную в том порядке, в котором они встречаются в массиве переменных, переданном методуPhase
. -
IntValueStrategy
— Правило выбора следующего значения для присвоения переменной. Здесь код использует значение по умолчаниюASSIGN_MIN_VALUE
, которое выбирает наименьшее значение, которое еще не было опробовано для переменной. Это присваивает значения в порядке возрастания. Другой вариант —ASSIGN_MAX_VALUE
, и в этом случае решатель будет присваивать значения в порядке убывания.