Constraint Programming

Constraint Programming (CP) is often called constraint logic programming or logic programming and has origins in artificial intelligence. Here the word "programming" refers to computer programming in a more traditional sense.

CP is similar to LP (Linear Programming) in that functions are used as constraints and the goal is typically to maximize or minimize an objective function. However, CP differs from LP in that Constraint Programming allows the constraint functions to be non-linear, and it provides the option of finding all possible combinations that satisfy a set of constraints rather than simply finding a maximal or minimal solution.

A common type of problem addressed by constraint programming is called a constraint satisfaction problem (CSP). A standard method of solving a CSP problem is through a technique known as domain reduction. In CSPs, all unknown variables are assigned a domain. The domain of a variable is all possible values to which the variable could be assigned. For example, the domain of a variable indicating the weight of a box could be [0..100] pounds while the domain of a variable indicating color of the box could be [Red, Blue].

Domain reduction is performed using "constraint propagation" which applies the constraints to reduce the domains of the variables to feasible values.

An example of using propagation to reduce domains follows:

Unknowns
     X={1,2,3,4,5,6,7,8,9,10}
     Y={1,2,3,4,5,6,7,8,9,10}
Constraints
     Y = 2X
     Y <= 10
     (X mod 2) = 1

Step 1: Apply Y=2X constraint to reduce domain of Y. Since Y must be a multiple of 2, remove all odd numbers from the domain of Y.

     X={1,2,3,4,5,6,7,8,9,10}
     Y={2,4,6,8,10}

Step 2: Apply Y <= 10 constraint to reduce domain of X. Since Y=2X and Y<=10, remove all numbers greater than 5 from X.

     X={1,2,3,4,5}
     Y={2,4,6,8,10}

Step 3: Apply (X mod 2)=1 constraint to further reduce domain of X

     X={1,3,5}
     Y={2,4,6,8,10}

Step 4: Since domain of X has changed, apply Y=2X constraint again to reduce Y

     X={1,3,5}
     Y={2,6,10}

Notice that all constraints are satisifed, but the values of X and Y are not known for certain. A searching technique can be used to obtain the exact values to use for X and Y.

Constraint Satisfaction Optimization Problems (CSOP) are an extension of CSP problems. Essentially, a CSOP is a CSP along with an objective function. Solving a CSOP typically has the goal of finding a solution that either maximizes or minimizes the objective function. For instance, our CSP could be extended to a CSOP by adding the goal of finding a solution that minimizes X + Y (X=1, Y=2).

Development Status

A stable version of the CSP solver component of the jOpt project has been released and is available for download.