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 simply 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 simple 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.
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: