OR-Tools provides two solvers for constraint programming (CP):

- The CP-SAT solver
- The original CP solver

The CP-SAT solver is technologically superior to the original CP solver and should be preferred in almost all situations. The exceptions are small problems for which solutions can be found quickly using either solver. In those cases you may find that the original CP solver outperforms CP-SAT.

## The CP-SAT solver

The CP-SAT solver is our recommended solver for constraint programming problems. We'll illustrate the CP-SAT solver using a simple example problem, in which there are:

- Three variables, x, y, and z, each of which can take on the values: 0, 1, or 2.
- One constraint: x ≠ y

The problem is to find all assignments of values to the variables for which x ≠ y.

The following sections describe a Python program that uses the CP-SAT solver to find all solutions for this example.

### Declare the model

The following code declares the CP-SAT model.

from ortools.sat.python import cp_model def main(): model = cp_model.CpModel()

`cp_model`

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 = model.NewIntVar(0, num_vals - 1, "x") y = model.NewIntVar(0, num_vals - 1, "y") z = model.NewIntVar(0, num_vals - 1, "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*.

model.Add(x != y)

### Create the solution printer

The CP-SAT solver displays the results using a *solution printer*.
The following code creates the solution printer.

print('\nNumber of solutions found: {}'.format(solution_printer.SolutionCount())) class SolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, variables): cp_model.CpSolverSolutionCallback.__init__(self) self.__variables = variables self.__solution_count = 0 def NewSolution(self): self.__solution_count += 1 for v in self.__variables: print('%s = %i' % (v, self.Value(v)), end = ' ') print() def SolutionCount(self): return self.__solution_count

The solution printer is a callback defined in a Python class. You pass the callback to the solver, as shown in the next section, and the callback is executed each time a new solution is found.

### Call the solver

The following code calls the solver.

solver = cp_model.CpSolver() solution_printer = SolutionPrinter([x, y, z]) status = solver.SearchForAllSolutions(model, solution_printer)

The CP-SAT solver takes as inputs both the model and a callback that is executed each time a new solution is found. In this example, the callback is the solution printer.

For any problem, the CP-SAT solver will return one of the following status values:

Status | Description |
---|---|

`OPTIMAL` |
An optimal feasible solution was found. |

`FEASIBLE` |
A feasible solution was found, but we don't know if it's optimal. |

`INFEASIBLE` |
The problem was proven infeasible. |

`MODEL_INVALID` |
The given CpModelProto didn't pass the validation step. You can get a
detailed error by calling `ValidateCpModel(model_proto)` . |

`UNKNOWN` |
The status of the model is unknown because a search limit was reached. |

### Results returned by the solver

Here are the 18 solutions found by the solver:

x = 1 y = 0 z = 0 x = 2 y = 0 z = 0 x = 2 y = 1 z = 0 x = 2 y = 1 z = 1 x = 2 y = 1 z = 2 x = 2 y = 0 z = 2 x = 2 y = 0 z = 1 x = 1 y = 0 z = 1 x = 0 y = 1 z = 1 x = 0 y = 1 z = 2 x = 0 y = 2 z = 2 x = 1 y = 2 z = 2 x = 1 y = 2 z = 1 x = 1 y = 2 z = 0 x = 0 y = 2 z = 0 x = 0 y = 1 z = 0 x = 0 y = 2 z = 1 x = 1 y = 0 z = 2 Number of solutions found: 18

### Complete code

Here is the complete code for the example using the CP-SAT solver.

from __future__ import print_function import collections from ortools.sat.python import cp_model def main(): model = cp_model.CpModel() # Create the variables. num_vals = 3 x = model.NewIntVar(0, num_vals - 1, "x") y = model.NewIntVar(0, num_vals - 1, "y") z = model.NewIntVar(0, num_vals - 1, "z") # Create the constraints. model.Add(x != y) # Call the solver. solver = cp_model.CpSolver() solution_printer = SolutionPrinter([x, y, z]) status = solver.SearchForAllSolutions(model, solution_printer) print('\nNumber of solutions found: {}'.format(solution_printer.SolutionCount())) class SolutionPrinter(cp_model.CpSolverSolutionCallback): """Print intermediate solutions.""" def __init__(self, variables): cp_model.CpSolverSolutionCallback.__init__(self) self.__variables = variables self.__solution_count = 0 def NewSolution(self): self.__solution_count += 1 for v in self.__variables: print('%s = %i' % (v, self.Value(v)), end = ' ') print() def SolutionCount(self): return self.__solution_count if __name__ == '__main__': main()

## Original CP solver

Next, we describe the original CP solver.

The following sections describe a Python program that finds all solutions to the simple example described above, 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-SAT.

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 default`CHOOSE_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 the`Phase`

method.`IntValueStrategy`

— The rule for choosing the next value to assign to a variable. Here the code uses the default`ASSIGN_MIN_VALUE`

, which selects the smallest value that hasn't already been tried for the variable. This assigns values in increasing order. Another option is`ASSIGN_MAX_VALUE`

, in which case the solver would assign values in decreasing order.