 Computing and Information Systems  Theses
Computing and Information Systems  Theses
Permanent URI for this collection
Search Results
Now showing
1  1 of 1

ItemCombinatorial reasoning for sets, graphs and document compositionGange, Graeme Keith ( 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 conflictdirected SAT solvers, allowing realworld problems to be solved in reasonable timeframes. Unfortunately, integrating new constraints into a lazy clause generation solver is a nontrivial exercise. Rather than building a propagator for every specialpurpose global constraint, it is common to express the global constraint in terms of smaller primitives. Multivalued decision diagrams (MDDs) can compactly represent a variety of common global constraints, such as REGULAR and SEQUENCE. We present improved methods for propagating MDDbased 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. sDNNF is an alternative representation which permits polynomial representation of a larger class of functions, while still allowing lineartime satisfiability checking. We present algorithms for integrating constraints represented as sDNNF 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 klayered 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 minimumheight table layout. We consider existing integerprogramming 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 realworld 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 nonoverlap of complex shapes, text containment and arbitrary separation. We demonstrate that these constraints can be solved quickly enough to allow direct manipulation.