Contributions to the integration of integer programming and constraint programming techniques

• Grant number: 12/09566-4
• Support Opportunities: Research Grants - Visiting Researcher Grant - International
• Start date: September 15, 2012
• End date: October 26, 2012
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cid Carvalho de Souza
• Grantee: Cid Carvalho de Souza
• Visiting researcher: John Norman Hooker
• Visiting researcher institution: Carnegie Mellon University (CMU), United States
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

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)