Constraint Programming page
Resources of the page:
  1. A very brief introduction to Constraint Programming (Section 1).

  2. C++ source code of a Traveling Salesman Problem constraint used in
    F. Focacci, A. Lodi, M. Milano, "A hybrid exact algorithm for the TSPTW", INFORMS Journal on Computing 14, 403-417, 2002 (Section 2).

  3. A list of pointers to CP references and CP tools (Section 3).

1  Introduction to CP

In the last decade Constraint Programming (CP) has shown its effectiveness in modeling and solving real-world combinatorial optimization problems. CP is a programming paradigm exploiting Constraint Satisfaction techniques ([4]), and in the following we restrict our attention to CP on Finite Domains (CP(FD)) which is the case of all constraint tools for discrete optimization such as CHIP ([1]), Ilog Solver ([7]), Eclipse ([6]), cc(FD) ([8]), CHOCO ([3]), etc.
The next paragraph briefly introduces the CP terminology that will be used in the remainder of the chapter. Complete definitions can be found in [5] (a complete textbook), and [2] (a basic introduction).
Combinatorial optimization problems are modeled through CP(FD) by means of a set of variables taking their value on a finite domain of integers, and are linked by a set of constraints. The constraints can be of mathematical or symbolic type, and in this second case, when they refer to a set of variables, are referred to as global constraints.
Global constraints typically model a well-defined part of the overall problem, where well-defined means that the same part has been recognized as a subproblem in several cases. A classic example of global constraint is the all_different(x1, ...,xn) constraint which imposes that variables x1, ..., xn must assume different values in a feasible solution.
To each constraint is associated a propagation algorithm aimed at deleting from variable domains the values that cannot lead to feasible solutions. Constraints interact through shared variables, i.e., as soon as a constraint has been propagated (no more values can be eliminated), and at least a value has been eliminated from the domain of a variable, say v, then the propagation algorithms of all the other constraints involving v are triggered ([4]).
Propagation algorithms are usually incomplete: once propagation is finished, there may remain some inconsistent values in the variable domains1. Therefore, unless the propagation phase ends with a fully instantiated solution or a failure (proving the problem inconsistent), a search phase is executed. One branching step is performed by partitioning the current problem (or the subproblem) into (easier) subproblems, e.g., by instantiating a variable to a feasible value in its domain. Propagation and search are interleaved in order to reach one or all feasible solutions.
As soon as a feasible solution improving the current best one is found, CP systems add a new constraint to the remaining search tree stating that further solutions should have a better value. This new constraint excludes leaf nodes from the remainder of the tree having a cost which is worse than the current one. Thus, CP solves a sequence of feasibility problems that improve the value of the objective function.
It is not difficult to see that the main advantage of using CP systems is flexibility: CP supports the design of declarative, compact and flexible models where the addition of new constraints is straightforward and does not affect the previous model. Indeed, the propagation of the previous constraints remain unchanged (since they locally model parts of the overall problem), and the previous constraints simply interact with the new ones through shared variables.

2  Solving the TSP with Time Windows

Abstract:
The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. We propose a hybrid approach for solving the TSPTW that merges Constraint Programming propagation algorithms for the feasibility viewpoint (find a path), and Operations Research techniques for coping with the optimization perspective (find the best path). We show with extensive computational results that the synergy between Operations Research optimization techniques embedded in global constraints, and Constraint Programming constraint solving techniques, makes the resulting framework effective in the TSPTW context also if these results are compared with state-of-the-art algorithms from the literature.

3  A not-exhaustive list of useful references

References

[1]
A. Aggoun and N. Beldiceanu. Extending CHIP in order to solve complex scheduling and placement problems. In Actes des Journees Francophones de Programmation et Logique, Lille, France, 1992.
[2]
F. Focacci, A. Lodi, M. Milano, and D. Vigo. An introduction to constraint programming. Ricerca Operativa, 91:5-20, 2000.
[3]
F. Laburthe. CHOCO: implementing a CP kernel. In CP'00 Post Conference Workshop on Techniques for Implementing Constraint programming Systems - TRICS. Singapour, 2000.
[4]
A. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977.
[5]
K. Marriott and P.J. Stuckey. Programming with Constraints. The MIT Press, 1998.
[6]
J. Schimpf, S. Novello, and H. Sakkout. IC-Parc ECLiPSe Library Manual, 1997.
[7]
Solver. ILOG Solver 5.0 User's Manual and Reference Manual. ILOG, S.A., 2000.
[8]
P. van Hentenryck, V. Saraswat, and Y. Deville. and evaluation of the constraint language cc(FD). Technical Report CS-93-02, Brown University, 1993.

Footnotes:

1Note that in the general case forcing acr consistency even for a single constraint is NP-hard.