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.
Tools
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.)
Examples
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.