# Constraint Optimization

Stay organized with collections Save and categorize content based on your preferences.

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.

## Tools

Google provides few ways to solve CP problems:

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.

[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]