Resources
Download
Questions/Slides/Installation instructions
Where?:
Objective
The goal of this course is to learn the use of tools to solve hard combinatorial optimisation problems by first modelling them in a solver-technology-independent constraint modelling language and then using an off-the-shelf constraint solver, as opposed to designing an (approximation) algorithm from first principles.
Motivation
Optimisation in general, and combinatorial optimisation in particular, is a service science, just like all of mathematics. Constrained combinatorial problems occur in many academic disciplines of science and technology, as well as in industry and society, and their effective modelling and efficient solving are of paramount importance there. Examples include resource allocation in communication systems, the routing of autonomous vehicles, the design of investment portfolios in financial mathematics, the verification and synthesis of electronic circuits, the design of scientific experiments, and the scheduling of experiments on shared hardware, and the identification of a minimum set of reactions to synthesise a given bio-molecule.
Unfortunately, the modern tools and methods of combinatorial (or: discrete) optimisation are mostly unknown outside computing or mathematicsdepartments, so that many opportunities for better solutions and/or shorter solving times are wasted, especially by the widespread mistaken belief that (NP-)hard problems cannot be solved at all or can at best only be tackled by greedy algorithms or by other sub-optimal algorithms.
Learning Outcomes
- model a combinatorial problem using a solving-technology-independent constraint-based modelling language;
- discuss models of a combinatorial problem expressed in a constraint-based modelling language;
- describe and compare constraint solving technologies that can be used by the back-end solvers to a constraint-based modelling language, including Boolean satisfiability (SAT) modulo theories (SMT), integer programming (IP), constraint programming (CP), and local search;
- decide which constraint solving technologies to try first when facing a new combinatorial problem, and motivate this decision;
- design and evaluate different models of a combinatorial problem for various constraint solving technologies.
The theory and algorithms underlying the constraint solvers used in this course will not be explained in depth, as specialised courses exist for this purpose, hence this course is also relevant for students in many research areas outside the IT departments, especially nowadays that combinatorial problems become more and more central to many research activities. Some background in discrete mathematics and, e.g., MatLab-style programming is required.
Course plan:
- Day 1, morning 9h30-12h00:
Combinatorial (satisfaction or optimisation) problems; MiniZinc: a constraint-based modelling language; Constraints; Modelling.
- Day 1, afternoon 13h00-16h00:
Basic Modelling, hands-on session (Please bring your own laptop).
- Day 2, morning 9h30-12h00:
Solving technologies; Advanced Modelling techniques.
- Day 2, afternoon 13h00-16h00:
Advanced Modelling, hands-on session (Please bring your own laptop).