Constraint Programming

Software Engineering; System-Level Programming

Constraint programming typically describes the process of embedding constraints into another language, referred to as the “host” language since it hosts the constraints. Not all programs are suitable for constraint programming. Some problems are better addressed by different approaches, such as logic programming. Constraint programming tends to be the preferred method when one can envision a state in which multiple constraints are simultaneously satisfied, and then search for values that fit that state.

Constraint programming tends to be used in situations where the “world” being programmed has multiple constraints, and the goal is to have as many of them as possible satisfied at once. The aim is to find values for each of the variables that collectively describe the world, such that the values fall within that variable's constraints.

A contrasting approach is the refinement model. Whereas the perturbation model assigns particular values to variables, under the refinement model, each variable can assume any value within its domain. Then, as time passes, some values of one variable will inevitably be ruled out by the values assumed by other variables. Over time, each variable's possible values are refined down to fewer and fewer options. The refinement model is sometimes considered more flexible, because it does not confine a variable to one possible value. Some variables will occasionally have multiple solutions.

A classic example of a problem that is especially well suited to constraint programming is that of map coloring. In this problem, the user is given a map of a country composed of different states, each sharing one or more borders with other states. The user is also given a palette of colors. The user must find a way to assign colors to each state, such that no adjacent states (i.e., states sharing a border) are the same color. Map makers often try to accomplish this in real life so that their maps are easier to read.

Those experienced at constraint programming can immediately recognize some elements of this problem. The most obvious is the constraint, which is the restriction that adjacent states may not be the same color. Another element is the domain, which is the list of colors that may be assigned to states. The fewer the colors included in the domain, the more challenging the problem becomes. While this map-coloring problem may seem simplistic, it is an excellent introduction to the concept of constraint programming. It provides a useful situation for student programmers to try to translate into code.

Constraint programming is an approach to problem solving and coding that looks only for a solution that works. It is not concerned with finding the optimal solution to a problem, a process known as “optimization.” Instead, it seeks values for the variables that fit all of the existing constraints. This may seem like a limitation of constraint programming. However, its flexibility can mean that it solves a problem faster than expected.

Another example of a problem for which constraint programming is well suited is that of creating a work schedule. The department or team contains multiple variables (the employees), each with their own constraints. Mary can work any day except Friday, Thomas can work mornings on Monday through Thursday but only evenings on Friday, and so forth. The goal is to simply find a schedule that fits all of the constraints. It does not matter whether it is the best schedule, and in fact, there likely is no “best” schedule.

—Scott Zimmer, JD