CP Solvers

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

Note that the CP-SAT solver is faster than the original CP solver.

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 solver

The following code declares the solver.

from ortools.sat.python import cp_model

def main():
  # Create the model and solver.
  model = cp_model.CpModel()
  solver = cp_model.CpSolver()

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 xy.

  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: %i' % solution_printer.SolutionCount())

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
  """Print intermediate solutions."""

  def __init__(self, variables):
    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.

  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:

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: 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():
  # Create the model and solver.
  model = cp_model.CpModel()
  solver = cp_model.CpSolver()
  # 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.
  solution_printer = SolutionPrinter([x, y, z])
  status = solver.SearchForAllSolutions(model, solution_printer)
  print('\nNumber of solutions found: %i' % solution_printer.SolutionCount())

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
  """Print intermediate solutions."""

  def __init__(self, variables):
    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, in case you need to modify existing code that uses it.

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.

Python
from ortools.constraint_solver import pywrapcp

def main():
  solver = pywrapcp.Solver("simple_example")
C++
#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.

Python
  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")
C++
  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 xy.

Python
  solver.Add(x != y)
C++
  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.

Python
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)
C++

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.

Python
  db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
  solver.Solve(db)
  print_solution(solver, x, y, z)
C++
  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.
See Decision builder for details.

Results returned by the solver

Here are the 18 solutions found by the solver:

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: 18

Complete code

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

Python
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()
C++
#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.

Send feedback about...

Optimization
Optimization