Title: Instance Space Analysis for the Quadratic Assignment Problem

Speaker: Dr Jeffrey Christiansen
The University of Melbourne

Summary:
The Quadratic Assignment Problem (QAP) is a combinatorial optimisation problem typically understood as a facility location problem. The QAP is NP-hard and it is often impractical to solve instances of even modest size with exact methods. Therefore, metaheuristics employing techniques such as genetic algorithms, iterated local search, and ant colony optimisation are employed in practice to find high-quality solutions for larger QAP instances. The performance of these metaheuristics varies depending on the characteristics of the particular instance being solved.

The research presented here applies Instance Space Analysis techniques to visualise the space of QAP test instances. The motivation for this work is twofold. First, we desire to assess the quality of coverage over the entire problem space provided by existing QAP benchmark libraries. In areas where the existing test libraries are deficient we investigate how they can be improved. Second, we want to improve understanding of the strengths and weaknesses of the algorithms tested, and in particular how to predict which algorithm will perform best on a particular instance based on easily-calculated properties of that instance.

Bio:
Dr Jeffrey Christiansen completed his PhD at RMIT in 2019, focusing on developing algorithms to solve discrete stochastic optimisation problems. His other research interests include metaheuristics, integer programming, and combinatorial optimisation, including both theoretical advancements and practical implementation. Jeffrey is presently a research fellow at Melbourne University with the OPTIMA ARC Training Centre.

—

SEMINAR: WED 30 APRIL 2025 16:00-17:00 (AEST, Melbourne Time)
ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635