Ciaran McCreesh: Modelling and optimisation, with graphs
Time: Mon 2019-04-01 12.00
Location: Room 4523, Lindstedtsvägen 5 - floor 5
Lecturer: Ciaran McCreesh
Lunch is served at 12:00 noon (register at
www.csc.kth.se/tcs/seminars/lunch/2019-04-01 at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.
There will be a more detailed technical discussionafter the seminar.
Constraint programming modelling languages and solvers make state of the art algorithms and optimisation research accessible to non-specialists. However, until now, working on graphs with constraint programming has involved awkward manual encodings and large performance trade-offs.
This talk will provide an overview of an ongoing project between the Universities of Glasgow, St Andrews, and Edinburgh, which covers high and low level modelling for optimisation problems that involve both graphs and non-graph constraints. I'll give examples of high level models for optimisation problems from metabolomics, healthcare, livestock epidemiology, and computer algebra, written in the Essence modelling language. I'll then give an overview of a suite of low-level dedicated subgraph solvers, and discuss how they differ from conventional constraint programming solvers. Finally, I'll explain how we intend to connect all these parts together, so we can combine the flexibility of constraint programming, the performance of dedicated subgraph solvers, and the convenience of high level modelling.
Following the break, I'll talk about symmetries. If one or more of the graphs in a model is symmetric, we might hope to be able to exploit this fact to reduce the amount of work needed to find a solution or to prove its optimality. I'll give examples of the different kinds of symmetries that can arise in graph problems, and show how these can be translated into additional constraints that can be provided to a solver. Most of this material will not require any background knowledge in group theory, although if there is interest, I can talk about the bigger picture.
The speaker was invited by Jakob Nordström.
For more information about upcoming seminars, visit www.kth.se/tcs/seminars-events