Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 1 of 1
-
ItemCombinatorial reasoning for sets, graphs and document composition( 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. Unfortunately, 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 common global constraints, such as REGULAR and SEQUENCE. We present improved methods for propagating MDD-based constraints, together with explanation algorithms to allow integration into lazy clause generation solvers. While MDDs can be used to express arbitrary constraints, some constraints will produce an exponential representation. s-DNNF is an alternative representation which permits polynomial representation of a larger class of functions, while still allowing linear-time satisfiability checking. We present algorithms for integrating constraints represented as s-DNNF circuits into a lazy clause generation solver, and evaluate the algorithms on several global constraints. Automated document composition gives rise to many combinatorial problems. Historically these problems have been addressed using heuristics to give good enough solutions. However, given the modest size of many document composition tasks and recent improvements in combinatorial optimization techniques, it is possible to solve many practical instances in reasonable time. We explore the application of combinatorial optimization techniques to a variety of problems which arise in document composition and layout. First, we consider the problem of constructing optimal layouts for k-layered directed graphs. We present several models models for constructing constructing layouts with minimal crossings, and with maximum planar subgraphs; motivated by aesthetic considerations, we then consider weighted combinations of these objectives – specifically,lexicographically ordered objectives (first minimizing one, then the other). Next, we consider the problem of minimum-height table layout. We consider existing integer-programming based approaches, and present A? and lazy clause generation methods for constructing minimal height layouts. We empirically demonstrate that these methods are capable of quickly computing minimal layouts for real-world tables. We also consider the guillotine layout problem, commonly used for newspaper layout, where each region either contains a single article or is subdivided into two smaller regions by a vertical or horizontal cut. We describe algorithms for finding optimal layouts both for fixed trees of cuts and for the free guillotine layout problem, and demonstrate that these can quickly compute optimal layouts for instances with a moderate number of articles. The problems considered thus far have all been concerned with finding optimal solutions to discrete configuration problems. When constructing diagrams, it is often desirable to enforce specified constraints while permitting the user to directly manipulate the diagram. We present a modelling technique that may be used to enforce such constraints, including non-overlap of complex shapes, text containment and arbitrary separation. We demonstrate that these constraints can be solved quickly enough to allow direct manipulation.