Combinatorial reasoning for sets, graphs and document composition
Graeme Gange · Minerva Access (University of Melbourne) · 2012
Combinatorial optimization problems require selecting the best solution from a discrete (albeit often extremely large) set of possible candidates. These problems arise in a diverse range of fields, and tend to be quite challenging. Rather than developing a specialised algorithm for each problem, however, modern approaches to solving combinatorial problems often involve transforming the problem to allow the use of existing general optimization techniques. Recent developments in constraint programming combine the expressiveness of general constraint solvers with the search reduction of conflict-directed SAT solvers, allowing real-world problems to be solved in reasonable time-frames. Un-fortunately, integrating new constraints into a lazy clause generation solver is a non-trivial exercise. Rather than building a propagator for every special-purpose global constraint, it is common to express the global constraint in terms of smaller primitives. Multi-valued decision diagrams (MDDs) can compactly represent a variety of