Natural optimisation modelling for software developers

© 2016 Dr. Kathryn Glenn FrancisConstraint solving technology has been successfully applied to large industrial combinatorial optimisation problems with high impact, but is not widely applied to smaller problems. Unfortunately, including even basic optimisation or constraint satisfaction functionality in an application currently requires the use of an entirely separate paradigm with which most software developers are not familiar. The aim of this thesis is to demonstrate the potential for an interface to a constraint solver which is much more approachable for general software developers, in order to promote wider use of the technology. Instead of defining a conventional constraint model directly, programmers use native code (in the application programming language) to define how to combine individual decisions to construct a candidate solution, and how to evaluate the result. Constraint satisfaction or optimisation is then seamlessly integrated into the wider application through automatic conversion between this definition and a conventional model solved by an external solver. We call this a native programming language interface. This thesis presents a prototype implementation of a native Java interface to a finite domain constraint solver, before exploring several ideas for improving the automated conversion from procedural code into an equivalent constraint model. This conversion process has already been studied in the context of software engineering applications, and the improvements discussed here should be transferable back to that domain. The following new techniques are presented.1. A novel query-based approach to handling destructive assignments, designed to improve the translation particularly when aliasing between variables is allowed. 2. An alternative technique (loop untangling) for creating copies of loop bodies in such a way that the uncertainty within the loop body is reduced, at the expense of a greater number of copies and an unknown execution order. 3. A new global constraint (reaching definitions) generalising the query-based translation technique to eliminate the assumption of a known order of execution for assignments (for use with loop untangling), and to achieve stronger deduction in some cases. To support these new techniques, two further contributions are included in the thesis. 1. A study into the circuit constraint, exploring how this constraint can be extended for the sub circuit/sub path case as required to constrain the execution path when using loop untangling, and how both versions can be implemented in a lazy clause generation constraint solver. 2. As part of the implementation of the reaching definitions constraint, discussion of how optional variables (solver variables which are allowed to take no value) can be implemented in a lazy clause generation solve