Next, we describe the original CP solver.
The following sections describe how to solve the example described in the CP-SAT section, this time using the original CP solver.
Declare the solver
The following code declares the solver.
from ortools.constraint_solver import pywrapcp def main(): solver = pywrapcp.Solver("simple_example")
#include "ortools/constraint_solver/constraint_solveri.h" namespace operations_research { void CPSimple() { // Instantiate the solver. Solver solver("CPSimple");
pywrapcp
is a Python wrapper for the underlying C++ solver.
Create the variables
The following code creates the variables for the problem.
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 numVals = 3; // Define decision variables. IntVar* const x = solver.MakeIntVar(0, numVals - 1, "x"); IntVar* const y = solver.MakeIntVar(0, numVals - 1, "y"); IntVar* const z = solver.MakeIntVar(0, numVals - 1, "z"); // Group variables into vectors. std::vector<IntVar*> allvars; std::vector<IntVar*> xyvars; allvars.push_back(x); xyvars.push_back(x); allvars.push_back(y); xyvars.push_back(y); allvars.push_back(z);
The solver creates three variables, x, y, and z, each of which can take on the values 0, 1, or 2.
Create the constraint
The following code creates the constraint x≠y.
solver.Add(x != y)
solver.AddConstraint(solver.MakeAllDifferent(xyvars));
Create the solution printer
The solver displays the results using a solution printer. The following code creates the solution printers.
def print_solution(solver, x, y, z): count = 0 while solver.NextSolution(): count += 1 print("x =", x.Value(), "y =", y.Value(), "z =", z.Value()) print("\nNumber of solutions found:", count)
void PrintSolution(Solver solver) { int count = 0; while (solver.NextSolution()) { count++; LOG(INFO) << "Solution " << count << ": x=" << x->Value() << " " << "y=" << y->Value() << " " << "z=" << z->Value() << " "; } LOG(INFO) << "Number of solutions: " << count; }
The solution printer for the original CP solver is a Python function that displays all solutions after the search has finished. (Note that this works differently than the solution printer for the CP-SAT solver.)
Call the solver
The following code calls the solver.
db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) solver.Solve(db) print_solution(solver, x, y, z)
DecisionBuilder* const db = solver.MakePhase(allvars, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE); solver.Solve(db); PrintSolution(solver);
The decision builder is the main input to the original CP solver. It contains the following:
vars
— An array containing the variables for the problem.- A rule for choosing the next variable to assign a value to.
- A rule for choosing the next value to assign to that variable.
Results returned by the solver
Here are the 18 solutions found by the solver:
x = 0 y = 1 z = 0 x = 0 y = 1 z = 1 x = 0 y = 1 z = 2 x = 0 y = 2 z = 0 x = 0 y = 2 z = 1 x = 0 y = 2 z = 2 x = 1 y = 0 z = 0 x = 1 y = 0 z = 1 x = 1 y = 0 z = 2 x = 1 y = 2 z = 0 x = 1 y = 2 z = 1 x = 1 y = 2 z = 2 x = 2 y = 0 z = 0 x = 2 y = 0 z = 1 x = 2 y = 0 z = 2 x = 2 y = 1 z = 0 x = 2 y = 1 z = 1 x = 2 y = 1 z = 2
Complete code
Here is the complete code for the example using the original CP solver.
from __future__ import print_function import sys from ortools.constraint_solver import pywrapcp def main(): solver = pywrapcp.Solver("simple_example") # 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") # Create the constraints. solver.Add(x != y) # Call the solver. db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) solver.Solve(db) print_solution(solver, x, y, z) def print_solution(solver, x, y, z): count = 0 while solver.NextSolution(): count += 1 print("x =", x.Value(), "y =", y.Value(), "z =", z.Value()) print("\nNumber of solutions found:", count) if __name__ == "__main__": main()
#include "ortools/constraint_solver/constraint_solveri.h" namespace operations_research { void CPSimple() { // Instantiate the solver. Solver solver("CPSimple"); const int64 numVals = 3; // Define decision variables. IntVar* const x = solver.MakeIntVar(0, numVals - 1, "x"); IntVar* const y = solver.MakeIntVar(0, numVals - 1, "y"); IntVar* const z = solver.MakeIntVar(0, numVals - 1, "z"); // Group variables into vectors. std::vector<IntVar*> allvars; std::vector<IntVar*> xyvars; allvars.push_back(x); xyvars.push_back(x); allvars.push_back(y); xyvars.push_back(y); allvars.push_back(z); // Define constraints. solver.AddConstraint(solver.MakeAllDifferent(xyvars)); // Create decision builder to search for solutions. DecisionBuilder* const db = solver.MakePhase(allvars, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE); solver.Solve(db); PrintSolution(solver); void PrintSolution(Solver solver) { int count = 0; while (solver.NextSolution()) { count++; LOG(INFO) << "Solution " << count << ": x=" << x->Value() << " " << "y=" << y->Value() << " " << "z=" << z->Value() << " "; } LOG(INFO) << "Number of solutions: " << count; } } // namespace operations_research // ----- MAIN ----- int main(int argc, char **argv) { operations_research::CPSimple(); return 0; }
Decision builder
The main input to the original CP solver is the decision builder, which contains the variables for the problem and sets options for the solver.
The code example above
creates a decision builder using the Phase
method
(corresponding to the C++ method
MakePhase
).
The term "Phase" refers to a phase of the search. In this simple example, there is just one phase, but for more complex problems, the decision builder can have more than one phase, so that the solver can employ different search strategies from one phase to the next.
The Phase
method has three input parameters:
vars
— An array containing the variables for the problem, which in this case is[x, y, z]
.IntVarStrategy
— The rule for choosing the next unbound variable to assign a value. Here, the code uses the defaultCHOOSE_FIRST_UNBOUND
, which means that at each step, the solver selects the first unbound variable in the order they occur in the variable array passed to thePhase
method.IntValueStrategy
— The rule for choosing the next value to assign to a variable. Here the code uses the defaultASSIGN_MIN_VALUE
, which selects the smallest value that hasn't already been tried for the variable. This assigns values in increasing order. Another option isASSIGN_MAX_VALUE
, in which case the solver would assign values in decreasing order.