The Dilemma of Constraint Programming

Constraint Programming is yet another application of the concept of Declarative Programming which is about describing a problem rather than devising an algorithm to solve it. Other examples of Declarative Programming include SQL, Linear Programming, HTML, XAML, SVG, and Regular Expressions. The idea is to let the user concentrate on formulating the problem rather than wasting a lot of efforts solving it. It opens the door for non-technical people to exploit the relatively cheap computing resources to solve real life problems that in the past would have required the cooperation of a team of subject experts and IT specialists to solve.

CP follows the same philosophy as LP but allows for a much greater expressive power. This means that problems that would be relatively difficult and tedious to formulate using LP are relatively straightforward when using CP. Example: Solving classic puzzles such as Sudoku or Zebra is relatively easy in CP but would require a complex Mixed Integer Programming (MIP) formulation, MIP being an extension of LP where some or all variables are assumed to be integers.

So, CP seems to be extremely exciting, until you tackle relatively simple problems such as Kuromasu and have a hard time formulating them in CP, for the simple reason that the required built-in constraints that would concisely describe the problem do not exist within any provided CP toolkit. As such you are left with two options:

  1. Formulate the problem using built-in constraints which proves to be quite convoluted loosing the theoretical ease of formulation, and inefficient because of the hundreds of constraints that have to be generated and ultimately managed by the solver at run time which may result in prohibitively long run times.
  2. Create user-defined constraints specifically tailored to the problem at hand: This requires understanding the internals of a specific solver such as Choco and implementing the new constraint using imperative programming, which in my opinion completely defeats the purpose of using CP as the declarative paradigm is mostly lost.

One might argue that it is still worth using CP as we may benefit from solvers that can transparently exploit prevalent multi-core CPU architectures. That argument might lose its strength as powerful API’s such as Java 7 Fork-Join and .Net Framework 4.0 Task Parallel Library (TPL) completely shield developers from the complexities of multithreaded programming.

Another aspect that hurts CP is the lack of a standard language and set of constraints so as to allow for portability and decoupling the API/Language from the solver. In LP, standard file formats such .MPS, and .LP allows feeding a problem to different solvers both proprietary and open-source. Moreover, high level languages such as AIMMS and AMPL can be used to model complex problems and use various solvers API’s to solve them. CP is badly in need of such mechanisms if it is to become as widely used as LP. Maybe, high level languages such as AIMMS and AMPL would gain into targeting CP solvers for particular classes of problems that are not well adapted to LP.

This article does not intend to be a CP bashing session. In fact, it stems from some good and bad experiences I had using CP and LP as I was so attracted by the Declarative Programming paradigm that I oversaw the obvious necessity to use the right tool for the right problem. For example, I tried to use LP to solve a scheduling problem and failed miserably as the solver was doing a completely blind search on a large computer generated MIP model (as no heuristics could be provided to guide the search). The other bad experience I had was solving Kuromasu using Choco CP API. It proved complex, inefficient and more difficult to implement than implementing a depth first search algorithm using Plain Old Java. Although I found a CP solution for Kuromasu, the “declarative” formulation was less than obvious and the run-time poor.

Conclusion: Do not use a hammer as a substitute for a screwdriver.

Leave a Reply