AAAI Publications, Tenth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
Modeling, Global Constraints, and Decomposition
J. Christopher Beck

Last modified: 2013-06-19

Abstract


Unlike mathematical programming and SAT solving, ConstraintProgramming (CP) is based on the idea that both modeling and solving of combinatorial optimization problems can be based on conjunctions of loosely coupled, recurring, combinatorial sub-problems (aka "global constraints"). This rich representational approach means that, for better or for worse, pretty much anything can be expressed as a global constraint. Much of CP's success, however, has come from exploiting only one aspect of the rich constraint definition: global constraint propagation. In this talk, I will investigate how work in CP, SAT, AI planning, and mathematical programming can be understood as more seriously pursuing the implications of a rich constraint definition and how the interplay between local and global information can lead to dynamic problem reformulations and a flexible hybrid solver architecture.

Full Text: PDF