Effective compilation of constraint models

Constraint programming (Computer science);

Rendl, Andrea ; Miguel, Ian ; Miguel, Ian

University:University of St Andrews

Department:Computer Science (School of)

关键词: Constraint programming (Computer science);   

Others  :  https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/973/Andrea%20Rendl%20PhD%20thesis.PDF?sequence=3&isAllowed=y

来源: DR-NTU

【 摘 要 】

Constraint Programming is a powerful technique for solving large-scale combinatorial (optimisation)problems. However, it is often inaccessible to users without expert knowledgein the area, precluding the wide-spread use of Constraint Programming techniques. Thisthesis addresses this issue in three main contributions.First, we propose a simple ‘model-and-solve’ approach, consisting of a framework wherethe user formulates a solver-independent problem model, which is then automatically tailoredto the input format of a selected constraint solver (a process similar to compiling ahigh-level modelling language to machine code). The solver is then executed on the input,solver, and solutions (if they exist) are returned to the user. This allows the user toformulate constraint models without requiring any particular background knowledge of therespective solver and its solving technique. Furthermore, since the framework can targetseveral solvers, the user can explore different types of solvers.Second, we extend the tailoring process with model optimisations that can compensate for awide selection of poor modelling choices that novices (and experts) in Constraint Programmingoften make and hence result in redundancies. The elimination of these redundanciesby the proposed optimisation techniques can result in solving time speedups of over anorder of magnitude, in both naive and expert models. Furthermore, the optimisations areparticularly light-weight, adding negligible overhead to the overall translation process.The third contribution is the implementation of this framework in the tool TAILOR, thatcurrently translates 2 different solver-independent modelling languages to 3 different solverformats and is freely available online. It performs almost all optimisation techniques thatare proposed in this thesis and demonstrates its significance in our empirical analysis.In summary, this thesis presents a framework that facilitates modelling for both expertsand novices: problems can be formulated in a clear, high-level fashion, without requiringany particular background knowledge about constraint solvers and their solving techniques,while (sometimes naturally occurring) redundancies in the model are eliminated for practicallyno additional cost, improving the respective model in solving performance by up toan order of magnitude.