From Declarative Models to Local Search

Sammanfattning: A solver is a general-purpose software for solving optimisation problems. It takes as input a description of a problem, called a model, and uses a collection of algorithms, called its solving technology, to ideally produce an optimal solution as output. Most solvers have a modelling language that cannot be processed by other solvers. This means that there is a risk of making an early commitment to a solver and its technology when writing a model. To address this risk, and to increase the accessibility of solvers, there has been a push for technology-independent modelling languages, a notable one being MiniZinc.A model written in MiniZinc is transformed by the MiniZinc toolchain in order to suit a targeted solver and its technology. However, for a solver to process a MiniZinc model, it also requires what is called a backend for MiniZinc. A backend translates the transformed MiniZinc model into the solver’s own modelling language and synthesises any components not in a MiniZinc model that the solver (or its technology) requires.The solving technology called constraint-based local search (CBLS) is based on the popular algorithm design methodology called local search, which often quickly produces near-optimal solutions, even to large problems. So, with the advent of CBLS solvers, there is a need for CBLS backends to modelling languages like MiniZinc.This thesis contributes to three research topics. First, it shows for the first time how to create a CBLS backend for a technology-independent modelling language, namely MiniZinc, and it shows that CBLS via MiniZinc can be competitive for solving optimisation problems. Second, it extends MiniZinc with concepts from local search, and shows that these concepts can be used even by other technologies towards designing new types of solvers. Third, it extends the utilisation of another technology, namely constraint programming, inside local-search solvers and backends.These contributions make local search accessible to all users of modelling languages like MiniZinc, and allow some optimisation problems to be solved more efficiently via such languages.