Discrete optimization over graph problems
AuthorDe Uña, Diego
AffiliationComputing and Information Systems
Document TypePhD thesis
Access StatusOpen Access
© 2018 Dr Diego De Uña
Discrete optimization problems are ubiquitous both in industry and theoretical computer science. They appear in a wide range of fields, such as manufacturing, planning, packing, design and scheduling. It is often the case that the problem at hand is in the form of a graph, or can be represented as such. It is therefore natural to have an interest in tackling this specific kind of problems. In this thesis we mainly use Constraint Programming as a technology to solve discrete optimization problems over graphs. We identify substructures that occur repeatedly in different problems that are usually tackled using Constraint Programming. We then study these combinatorial substructures to develop advanced algorithms within Constraint Programming solvers that attempt to drastically reduce the time spent by solvers on the problem. These are called propagators, and this thesis explores a series of them that deal with graph structures. All these algorithms have been implemented and different set of experiments show the value of each one of them. We also investigate the use of graphical structures not as a tool to represent the model, but rather as a tool within a Constraint Programming solver to increase its performance when tackling highly constrained problems. We do so through the use of Multi-valued Decision Diagrams (MDD) and Deterministic Decomposable Negation Normal Form Formulae (d-DNNF) for which propagators already exist. Our work on this focuses on improving the model provided by a user of the solver, by preprocessing parts of it in the hope of decreasing the total runtime. Additionally, we identified a graph problem in the field of computational sustainability for which Constraint Programming solvers were not adequate. In order to solve this problem, we developed a completely new Local Search algorithm that was specifically designed for it. The common thread between all components of this thesis are graphs and discrete optimization. We have looked at how to improve Constraint Programming technology to solve discrete problems containing graphs, how to use graphs within Constraint Programming to solve any discrete problem, and lastly, how to tackle discrete graph problems when Constraint Programming is not an adequate tool.
Keywordsconstraint programming; graph theory; MDD; d-DNNF
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References