Original CP Solver

This section describes the original constraint programming solver, which has been replaced by the superior CP-SAT solver.

Note: We recommend using the CP-SAT solver rather than 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.

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 x≠y.

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:

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 program

Here are the complete programs for the example using the original CP solver.

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.