Combinatorial problems are those where a set of decisions that satisfy a given set of constraints, must be selected from a set of possible combinations. Solving these problems is critical in a wide range of areas, such as telecommunications, circuit design and transportation. It is also remarkably hard, which is why many solving techniques exist, each with their own strengths and weaknesses. High-level modelling languages allow combinatorial problems to be specified as high-level models that can then be compiled into different low-level programs, each suitable for a solving technique. While the high-level modelling and solver-independence characteristics of these languages are very useful for modellers, they make it difficult for the compiler to yield programs that can be solved efficiently. Further, changes to a model can have a significant and unexpected impact on the efficiency of the resulting programs. This makes the modelling, compilation, and solving of combinatorial problems a challenging iterative process.

This thesis states that information regarding the implicit and explicit structure present in a model can be very beneficial for this challenging process, as it allows users, compilers and solvers to make better decisions during modelling, compilation, and solving. The main objective of the thesis then, is to effectively take advantage of structure in constraint models to improve the modelling, compilation, and solving process. To achieve this, a new framework is proposed for exploring how structural information can be discovered, shared, and generalised between different stages of the process. In particular, the framework is used as a guide to determine whether the explicit structure of a model can be used to (a) improve the quality of compiled programs; (b) guide the search for and exposure of hidden implicit structure; and (c) help identify parts of a model that are incorrectly formulated.

This is achieved by the following three main contributions of this thesis. First, a method that preserves model structure deeper into the compilation process, thus enabling more efficient programs to be produced. Second, a method for finding implicit structure that can be made explicit in a model, thus making modelling easier. And third, a method that uses preserved model structure to help explain why a model is unsatisfiable, thus helping users produce correct models. These three methods have been implemented and evaluated for the MiniZinc language. The experimental results show them to be effective in practice. Together, these contributions help make high-level modelling a more powerful and attractive approach for solving hard combinatorial problems.