Speaker: Adam Letchford, Lancaster University

Website: https://www.lancaster.ac.uk/staff/letchfoa/

Title: Progress on the uncapacitated facility location problem

Abstract: The Uncapacitated Facility Location Problem, also known as the Simple Plant Location Problem, is a classic combinatorial optimization problem.  It also happens to be strongly NP-hard.  A remarkably wide variety of solution techniques have been applied to it. This includes exact methods (such as integer programming, dual ascent, dual adjustment, Lagrangian relaxation and semi-Lagrangian relaxation), heuristics (such as greedy constructive heuristics, local search, tabu search, variable neighbourhood search and genetic algorithms), and approximation algorithms.  The first half of this talk will be spent surveying the (considerable) literature on the problem. After that, I will go on to discuss some projects that I have been involved in, concerned with polyhedra, lower-bounding procedures and exact algorithms.  Some of these projects were conducted with my former PhD student, Sebastian Miller, and/or Dr Laura Galli, who is now at the University of Bologna.

Host: Michael Malmros Sørensen

Organisers: Surabhi Verma and Hartanto Wong