Contributions to the integration of integer programming and constraint programming techniques

Abstract

Research over the last decade or more shows that integration of integer programming (IP) and constraint programming (CP) methods can yield substantial benefits in the solution of combinatorial optimization problems. These include orders-of-magnitude reductions in computation time for some important problems in the field, as well as a more powerful modeling approach. In this project we propose to focus on a central element of integrated methods, namely the development of polyhedral relaxations for "global constraints" used in CP. Global constraints are key to the success of CP. They represent highly structured subsets of constraints. By processing each global constraint with a specialized “filtering'' algorithm, the solver can exploit problem substructure to exclude infeasible values of the variables. A logical next step is to combine the advantages of global constraints with the relaxation technology of IP, by studying the polyhedral structure of global constraints. The study described in this proposal fits in this context. (AU)