Thursday 17 Nov 2016The Fitness Landscape of Combinatorial Optimisation Problems

Adam Prugel-Bennett - University of Southampton

Harrison 170 14:30-15:30

Combinatorial optimisation problems are an important set of problems with many practical applications. Many heuristic search algorithms have been designed to solve these. However, do we have any right to believe that these search strategy should work? In this talk we describe our attempt to study the landscapes of a number of classical optimisation problems. In particularly, we study instances of MAXSAT, Graph-colouring, TSP and Quadratic Assignment Problem. Despite their many differences we show that there is a lot of commonality in the large-scale structure of these problems. This provides some optimism that common research heuristics are likely to be effective on a large number of problems that we are likely to face.

Add to calendar

Add to calendar (.ics)