Enhancing the performance of constraint programming through the introduction of linear programming

Constraint Programming (CP) has been successful in a number of combinatoria l search and discrete optimisation problems. Yet other more traditional app roaches, such as Integer Programming (IP), can still give a better performa nce on the same problem types. Central to IFS success is its reliance an a fast Linear Programming (LP) solver providing solutions during the search t o the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integra lity. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examine d here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is conf igured and run on these problems. The outcome shows that using the LP solve r within the CP search is a valuable addition to the available search strat egies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IF. Overall, CP + L P can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.