Constraint Optimization

Constraint optimization, or constraint programming (CP), is the name given to identifying feasible solutions out of a very large set of candidates, where the problem can be modeled in terms of arbitrary constraints. CP problems arise in many scientific and engineering disciplines. (The word "programming" is a bit of a misnomer, similar to how "computer" once meant "a person who computes". Here, "programming" refers to the arrangement of a plan , rather than programming in a computer language.)

CP is based on feasibility (finding a feasible solution) rather than optimization (finding an optimal solution) and focuses on the constraints and variables rather than the objective function. In fact, a CP problem may not even have an objective function — the goal may be to narrow down a very large set of possible solutions to a more manageable subset by adding constraints to the problem.

An example of a problem that is well-suited for CP is employee scheduling. The problem arises when companies that operate continuously — such as factories — need to create weekly schedules for their employees. Here's a very simplified example: a company runs three 8-hour shifts per day and assigns three of its four employees to different shifts each day, while giving the fourth the day off. Even in such a small case, the number of possible schedules is huge: each day, there are 4! = 4 * 3 * 2 * 1 = 24 possible employee assignments, so the number of possible weekly schedules is 247, which is over 4.5 billion. Usually there will be other constraints that reduce the number of feasible solutions — for example, that each employee works at least a minimum number of days per week. The CP method keeps track of which solutions remain feasible when you add new constraints, which makes it a powerful tool for solving large, real-world scheduling problems.

CP has a widespread and very active community around the world with dedicated scientific journals, conferences, and an arsenal of different solving techniques . CP has been successfully applied in planning, scheduling, and numerous other domains with heterogeneous constraints.


Google provides few ways to solve CP problems:

  • CP-SAT solver: A constraint programming solver that uses SAT (satisfiability) methods.
  • Original CP solver: A constraint programming solver used in the routing library.

If your problem can be modeled with a linear objective and linear constraints, then you have a linear programming problem and should consider MPSolver. (However, routing problems are typically best solved with our vehicle routing library even if they can be represented with a linear model.)


The next section describes the CP-SAT solver, the primary OR-Tools solver for constraint programming. (SAT stands for satisfiability: the solver uses techniques for solving SAT problems along with CP methods.)

Here are some examples of scheduling problems that are well-suited for the CP-SAT solver:

Two classic CP problems are the N-queens problem and cryptarithmetic puzzles.