SEMINAR: “HIGH LEVEL MODELING IN CONSTRAINT PROGRAMMING” BY ÖZGÜR AKGÜN, PhD.

Seminar by Özgür Akgün on August 14, 2018 Tuesday 14:00 at Y-212

Abstract:

Combinatorial problems appear everywhere: from theoretical problems in mathematics to very practical problems in manufacturing and logistics. Several disciplines offer ways of solving combinatorial problems: operations research, Boolean satisfiability solving, constraint programming, meta-heuristics, etc. No matter what the solution method is, the formulation (or model) of the problem is critical to the efficiency of the solver. Automating the modelling process has long been of interest because of the expertise and time required to produce an effective model of a given problem.

I describe a method to automatically produce concrete models from an abstract problem specification written in Essence. The approach is to incrementally refine the specification by applying rewriting rules. Any non-trivial problem specification may be refined in multiple ways, creating a space of models from which to choose. The concrete models may then be solved using one of many available solvers.

This approach is implemented in a system called Conjure. The models produced by Conjure are compared to hand-written models from the literature that are known to be effective. Empirical results confirm that Conjure can reproduce successfully the kernels of the constraint models of several benchmark problems found in the literature.

Short Bio:

Özgür Akgün is a Lecturer of Computer Science at the University of St Andrews. His main research interest is in automated decision making and optimization, specifically constraint programming and high-level modelling. Dr Akgün studied at the Izmir University of Economics for his undergraduate degree and obtained his PhD at the University of St Andrews.