Advanced search
Start date
Betweenand

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)

Articles published in Agência FAPESP Newsletter about the research grant:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)