Department of Mathematics

Seminar, Speaker: Pierre Flener Title: Solving Discrete Optimisation Problems Without Knowing How

  • Date: 4/5/2017 at 11:00 AM
  • Location: Polacksbacken ITC/1211
  • Lecturer: Pierre Flener
  • Contact person: Di Yuan
  • Seminarium

Speaker: Pierre Flener

Title: Solving Discrete Optimisation Problems Without Knowing How

Abstract: Unbeknownst to many, it has become possible to model discrete (or: combinatorial) optimisation problems in a language that is interfaced with solvers of multiple optimisation technologies, none of which dominates the others or shares a modelling language with them, such as mixed-integer programming (MIP), Boolean satisfiability (SAT), SAT modulo theories (SMT), constraint programming (CP), stochastic local search (SLS), etc, as well as hybrids thereof.  It is now possible to model the constraints and objective function of a problem upon learning a single fully declarative high-level modelling language and, upon experiments with solvers of different technologies, to choose a winning technology and solver, without knowing how the problem is solved.

I present one such language, called MiniZinc, to the toolchain of which my research group is making significant contributions.  I show how the high-level MiniZinc abstractions of common combinatorial structures enable highly readable short models of complex problems. These often non-linear abstractions are translated into linear (in)equalities over integer variables, into clauses over Boolean variables, etc, using well-known encodings. This allows modellers to reuse these encodings systematically rather than tediously or erroneously rediscovering them.

For most managers, engineers, and scientists the time to achieve a particular solution speed or quality is drastically reduced by such model-once-solve-everywhere toolchains.