The CP Solver

OR-Tools implements constraint programming (CP) with the CP solver. In the following sections, we introduce the CP solver by a simple example. After that, we present Python and C++ programs that find all feasible solutions to the problem using the CP solver.

A brief introduction to the CP solver

We start by defining the type of problem the CP solver is designed to solve. A CP problem consists of the following:

  • A set of variables, and for each variable, a set of values that it can take on. The set of all possible assignments of values to the variables is called the search space for the problem.
  • Contraints — a set of rules that specify whether a given assignment of values to the variables is a feasible (allowed) solution.
The CP problem is to find all feasible solutions.

A simple CP problem

Let's start with a very simple CP 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.

Since each variable can take on three possible values, the size of the search space is 3 · 3 · 3 = 27. In theory, the solver has to check every possible assignment in the search space. But in practice, many assignments are ruled out by the constraints.

To solve this problem, the CP solver systematically tries the possible assignments of values to the variables, and checks to see which ones are feasible. While this may sound straightforward, there are a lot of decisions the solver has to make during the search — in particular, the order in which it assigns values to variables.

Bound and unbound variables

At the beginning of the search, none of the variables has an assigned value — we say that they are unbound. When the solver assigns a value to a variable, the variable is bound. During the search, the status of each variable changes from unbound to bound and vice-versa many times as the solver tries different combinations of values.

Assigning values to variables

Each time the solver makes a variable assignment, it has a couple of choices to make, which you control with the solver options:

  • If there are any unbound variables, which one should it choose to assign a value to next? By default, it chooses the first unbound variable, in the order in which you pass them to the solver. (However, there are other options.)
  • Having chosen an unbound variable, which of the values that have not yet been tried (for the current values of the bound variables) should it assign to the variable? In this example, the solver chooses the smallest value. But in other problems, you might want the solver to choose the largest value, or one in the middle.

Let's see how this might go in the simple problem given above. Assuming you pass the variables to the solver as an array [x, y, z], by default the solver chooses the first unbound variable, which is x.

Next, the solver has to decide which value to assign to x. In this example, it assigns the smallest value: 0. After that, the solver moves on to the remaining unbound variables, y and z, and assigns them 0 as well. Once all the variables are bound, the solver checks whether the assignment is feasible — it isn't, because x = y, violating the constraint.

Backtracking

Since the infeasible assignment x = 0, y = 0, z = 0 is ruled out by a constraint (x ≠ y) that doesn't involve z, the solver doesn't need to try other values of z with the current values of the bound variables. So it unsets the value of z (making it unbound) and goes back to the last bound variable, y. Moving back in the search tree this way is called backtracking. The solver then changes the value of y to the smallest untried value, which is now 1. At this point, the bound variables are x = 0 and y = 1.

A feasible solution

Next, the solver returns to the now unbound variable z, and assigns it the value 0, which is the smallest value that hasn't been tried with the current values of the bound variable. (While 0 was tried with the previous values x = 0 and y = 0, it has not yet been tried with the values x = 0 and y = 1.) Now the solver has found a feasible solution: x = 0, y = 1, z = 0.

The solver continues in this way until it has tried all the possible assignments of the variables. Of course, the solver does a lot more along the way, which we'll describe in greater detail in the section The N-queens problem. But for now, this simple example should give you a general idea of how the CP solver works.

CP solver reference page

You can find detailed information about the C++ methods available for the CP solver in the solver's C++ Reference page.

Calling a method in the other supported languages (Python, Java, or Sharp) invokes the underlying C++ method. There are some minor differences between the names of methods and parameters in the different languages. As an example, the following table shows the names corresponding to the C++ method MakeIntVar in the four languages.

C++ Java C# Python
MakeIntVar makeIntVar MakeIntVar IntVar
Note that for C++ methods that begin with "Make," the corresponding Python method names usually omit "Make." This is also true from some C# method names.

Python and C++ programs

The following sections describe Python and C++ programs that find all feasible solutions to the example problem.

Declare the CP solver

The following code declares the CP solver.

Python solver
from ortools.constraint_solver import pywrapcp

def main():
  # Creates the solver.
  solver = pywrapcp.Solver("simple_example")
C# solver
#include "ortools/constraint_solver/constraint_solveri.h"

namespace operations_research {

void CPSimple() {
  // Instantiate the solver.
  Solver solver("CPSimple");
In the Python code, pywrapcp is a wrapper for the underlying C++ solver.

Create the variables

You can create integer variables for a CP problem using the IntVar method (corresponding to the C++ method MakeIntVar). The following code creates three variables, x, y, and z. The first two arguments of IntVar give a lower and upper bound on the possible values of the variables, so in this case the variables can equal 0, 1, or 2.

Python solver
# Creates 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")
C# solver
  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);

Note that in the C++ program, it is necessary to create one array for all the variables, [x, y, z], and another for just the variables [x, y]. The latter array is used to create the constraint.

Create the constraint

The following code creates the constraint for the problem.

Python solver
  solver.Add(x != y)
C# solver
  solver.AddConstraint(solver.MakeAllDifferent(xyvars));

In the C++ version, the constraint is created using the AllDifferent method (corresponding to the C++ method MakeAllDifferent), which requires the variables x and y, contained in the array xyvars, to be different. Note that the method is not applied to the array allvars, as this would require x ≠ y, y ≠ z, and x ≠ z, which is more restrictive than we want.

Decision builder

A key input to the solver is the decision builder, which sets options for the order in which the solver assigns values to the variables. In larger problems, these options can significantly reduce the search time.

The following code creates a decision builder using the Phase method (corresponding to the C++ method MakePhase).

  db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
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.

Call the solver and display the results

The following code calls the solver, with the decision builder db as an input argument, and displays the results.

Python solver
  solver.Solve(db)
  count = 0

  while solver.NextSolution():
    count += 1
    print("Solution", count, '\n')
    print("x = ", x.Value())
    print("y = ", y.Value())
    print("z = ", z.Value())
    print()
  print("Number of solutions:", count)
C# solver
      solver.Solve(db);
  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;
Here are the 18 solutions found by the search:
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 in Python and C#.

Full Python program
from __future__ import print_function
import sys
from ortools.constraint_solver import pywrapcp

def main():
  # Creates the solver.
  solver = pywrapcp.Solver("simple_example")
# Creates 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)
# Create the decision builder.
  db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
  solver.Solve(db)
  count = 0

  while solver.NextSolution():
    count += 1
    print("Solution", count, '\n')
    print("x = ", x.Value())
    print("y = ", y.Value())
    print("z = ", z.Value())
    print()
  print("Number of solutions:", count)

if __name__ == "__main__":
  main()
Full C# program
#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);
  // Search.
  solver.Solve(db);
  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;
}

Combining constraints by "and" versus "or"

Any pair of constraints in an optimization problem can be combined by "and" or "or." We'll explain how to combine constraints both ways.

As an illustration, let's add a second contraint to the preceding example. The constraints are now

  • x ≠ y
  • y ≠ z

The following sections show how to combine these two constraints by "and" and by "or":

Combining constraints by "and"

Combining two constraints by "and" is simple — just apply the solver.Add method twice. For example

solver.Add(x != y)
solver.Add(y != z)
The solver searches for solutions for which both constraints hold. When you run the program with the constraints shown above, it returns the 12 solutions for which x != y and y != z.

Solution 1

x =  0
y =  1
z =  0

Solution 2

x =  0
y =  1
z =  2

Solution 3

x =  0
y =  2
z =  0

Solution 4

x =  0
y =  2
z =  1

Solution 5

x =  1
y =  0
z =  1

Solution 6

x =  1
y =  0
z =  2

Solution 7

x =  1
y =  2
z =  0

Solution 8

x =  1
y =  2
z =  1

Solution 9

x =  2
y =  0
z =  1

Solution 10

x =  2
y =  0
z =  2

Solution 11

x =  2
y =  1
z =  0

Solution 12

x =  2
y =  1
z =  2
Combining constraints by "or"

To combine the two constraints by "or," use the method solver.Max as follows:

solver.Add(solver.Max(x != y, y != z) == 1)
Since the numerical value corresponding to True is 1, while False is 0, solver.Max acts as a logical "or" between Boolean conditions. That is, solver.Max(x != y, y != z) equals 1 if either x != y or y != z, and 0 otherwise. As a result, the code above adds the constraint x != y or y != z.

With this constraint, the program returns the 24 solutions for which x != y or y != z.

Solution 1

x =  0
y =  0
z =  1

Solution 2

x =  0
y =  0
z =  2

Solution 3

x =  0
y =  1
z =  0

Solution 4

x =  0
y =  1
z =  1

Solution 5

x =  0
y =  1
z =  2

Solution 6

x =  0
y =  2
z =  0

Solution 7

x =  0
y =  2
z =  1

Solution 8

x =  0
y =  2
z =  2

Solution 9

x =  1
y =  0
z =  0

Solution 10

x =  1
y =  0
z =  1

Solution 11

x =  1
y =  0
z =  2

Solution 12

x =  1
y =  1
z =  0

Solution 13

x =  1
y =  1
z =  2

Solution 14

x =  1
y =  2
z =  0

Solution 15

x =  1
y =  2
z =  1

Solution 16

x =  1
y =  2
z =  2

Solution 17

x =  2
y =  0
z =  0

Solution 18

x =  2
y =  0
z =  1

Solution 19

x =  2
y =  0
z =  2

Solution 20

x =  2
y =  1
z =  0

Solution 21

x =  2
y =  1
z =  1

Solution 22

x =  2
y =  1
z =  2

Solution 23

x =  2
y =  2
z =  0

Solution 24

x =  2
y =  2
z =  1

A Python program that illustrates both ways of combining constraints

The following program combines the two constraints using both "and" and "or," and displays the results in each case.

from __future__ import print_function
import sys
from ortools.constraint_solver import pywrapcp

def main(comb):
  # Creates the solver.
  solver = pywrapcp.Solver("simple_example")
# Creates 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.
  label = ''     # Label for displaying results.

  if comb is 'A_and_B':
    # Combine constraints by "and."
    solver.Add(x != y)
    solver.Add(y != z)
    label = 'Solutions for which x != y and y != z:'

  elif comb is 'A_or_B':
    # Combine constraints by "or."
    solver.Add(solver.Max(x != y, y !=z ) == 1)
    label = 'Solutions for which x != y or y != z:'
# Create the decision builder.
  db = solver.Phase([x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
  solver.Solve(db)
  print(label)
  print()
  count = 0

  while solver.NextSolution():
    count += 1
    print("Solution" , count, '\n')
    print("x = ", x.Value())
    print("y = ", y.Value())
    print("z = ", z.Value())
    print()
  print("Number of solutions: ", count)

# Boolean combinations for two statments:
# A: x != y
# B: y != z
boolean_combs = ['A_and_B', 'A_or_B']

if __name__ == "__main__":
  for comb in boolean_combs:
    main(comb)

Enviar comentarios sobre…