Operations Research Meets Constraint Programming: Some Achievements So Far

This paper reports promising algorithms that have been built on top of both operations research (OR) and constraint programming (CP) research. First we describe Guided Local Search (GLS), a penalty-based meta-heuristic algorithm that sits on top of local search algorithms and helps them to escape local optima. Then we describe Fast Local Search (FLS), a strategy that reduces the size of the neighbourhood. GLS and FLS have been demonstrated to be highly successful in a number of non-trivial problems, including commercial applications. We shall also, in this paper, report selected promising research by other groups in combining OR and CP ideas -- namely (a) Lagrangian Method and (b) fine-grain interaction between mixed integer programming (MIP) and finite domain constraint propagation. The main message that we want to convey in this paper is: there is no real boundary between OR and CP. In fact, OR has already become an important part of CP and a great deal can be gained by cross-fertil..