[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publication: [PUBLink])

The mathematical framework of operations research and the propositional formulas of SAT are highly restricted. The problems must be translated into a very specific form, which can only be done by experts. On the other hand, constraint programming allows the use of higher-level constraints, which make it easier to model a problem.

The OR and SAT approach is to break the problems down into their specific frameworks and to then scan the resulting specifications for structures on which to apply specific solution strategies. Although many efficient methods have been developed, the propositional clauses of SAT and the linear inequations of OR are scarcely able to exploit higher-level domain knowledge to support search (see also [PUBLink]). This is not the case for constraint programming. The advantage of this higher-level approach may be the reason for the superiority of constraint programming in domains like job-shop scheduling where powerful constraints are available - such as the cumulative constraint for resource-assignment problems that allows the application of specific technologies like edge finding [PUBLink] [PUBLink] [PUBLink] [PUBLink]. However, current constraint-based approaches that use local search do not normally exploit domain knowledge (see Chapter [Using Global Constraints for Local Search]).

The SAT approach does not have numbers in its representation repertoire. The propositional SAT variables can therefore represent only qualitative differences - unlike CP and OR which can also represent quantitative information. Of course, discrete numbers can also be modeled in SAT by using a propositional variable for each value of the discrete domain. But this is a highly unsuitable approach, not only because of its costs but also because the values' ordering relation is often exploited during search.

Another reason for not using OR is that there are lots of planning decisions with discrete alternatives, and the performance of OR methods declines sharply as the number of integer variables increases. There are initial approaches aiming to combine constraint programming and OR solution methods (e.g., [PUBLink] [PUBLink]), but because the combination of these paradigms is not our main concern, we confine our contention to constraint programming. Some tentative work has also been done on combining SAT with linear inequalities (see [PUBLink]).

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek