Global Constraints

The integration of methods from mathematical programming, algorithm theory, and constraint programming has recently yielded to significant improvements in the efficiency of filtering algorithms that play an essential part when solving hard combinatorial problems. We consequently pursue this successful line of research. One important trend regards the development of powerful, so-called global constraints. They are very appealing because of two different aspects. First, they facilitate problem modeling, because problem specification becomes a much more intuitive process when larger semantic building blocks offer more expressiveness, which is essential in order to facilitate access to computational optimization support. Second, global constraints allow the solver to be aware and to exploit problem structure that does not need to be crushed into pieces to adapt for a modeling language of limited expressiveness — as it is the case, for instance, in mathematical programming, where all problems must be stated as conjunction of linear inequalities. For constraints that capture important structures that recur frequently as substructures of real-world problems and for generally applicable constraints of high expressiveness, within Cornflower we devise propagation algorithms for the corresponding global constraints.



Related Publications