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.

To achieve this state, programmers use one of two main approaches. The first approach is the perturbation model. Under this model, some of the variables are given initial values. Then, at different times, variables are changed (“perturbed”) in some way. Each change then moves through the system of interrelated variables like ripples across the surface of a pond: other values change in ways that follow their constraints and are consistent with the relationships between values. The perturbation model is much like a spreadsheet. Changing one cell's value causes changes in other cells that contain formulas that refer to the value stored in the original cell. A single change to a cell can propagate throughout many other cells, changing their values as well.

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.

Constraint programming is a major departure from more traditional approaches to writing code. Many programmers are more familiar with imperative programming, where commands are issued to the computer to be executed, or functional programming, where the program receives certain values and then performs various mathematical functions using those values. Constraint programming, in contrast, can be less predictable and more flexible.

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