Advanced search
Start date
Betweenand

Contributions to the integration of integer programming and constraint programming techniques

Grant number: 12/09566-4
Support type:Research Grants - Visiting Researcher Grant - International
Duration: September 15, 2012 - October 26, 2012
Field of knowledge:Physical Sciences and Mathematics - Computer Science
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
Home 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)