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.

### 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

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 C#) 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` |

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

from ortools.constraint_solver import pywrapcp def main(): # Creates the solver. 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 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.

# 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")

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.

solver.Add(x != y)

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.

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)

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;

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

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()

#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 constraints by "or"
- A Python program that illustrates both ways of combining constraints

**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)