Merging Combinatorial Design and Optimization: the Oberwolfach Problem

Speaker:  Fabio Salassa - Politecnico di Torino
  Wednesday, November 13, 2019 at 2:30 PM

Combinatorial optimization is a subset of mathematical optimization that is related to operations research, algorithm theory, and computational complexity theory. It consists of finding an (optimal) object from a finite set of objects and in many such problems, exhaustive search is not tractable. Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. Combinatorial Design and Combinatorial Optimization, though apparently different research fields, share common problems, such as for example sudokus, covering arrays, tournament design and more in general problems that can be represented on graphs.
Aim of the talk is to present intersections and possible contributions to Combinatorial Design given by the application of Combinatorial Optimization techniques and solution methods. This is accomplished by the presentation of results on the Oberwolfach Problem (OP) where interaction of methods from both domains enabled us to solve large OP instances in limited computational time and at the same time to derive a theoretical result for general classes of instances.


Contact person
Giuseppe Mazzuoccolo

Publication date
October 8, 2019

Studying