Solving Uncapacitated Facility Location and Network Design Problems
Speaker: Mr Robin Pearce
There are a large number of problems in industrial optimisation which can be considered facility location and network design problems. In many cases, the problem involves routing a series of requests from specific origins to a set of potential destinations. If a few conditions are met, such as the facilities and arcs being uncapacitated, then the problem may fall under the umbrella of Uncapacitated Facility Location and Network Design Problems (UFLNDP). All of these problems have a nice property in common: they are excellent candidates for disaggregated Benders decomposition.
If a design for the network is given, solving the routing problem reduces to a collection of shortest-path problems. Using linear programming duality, information about the dependency of the routing cost on the network design can be passed to the master problem to find a better network design. This is repeated until an optimal design for the network is found. Benders decomposition is particularly powerful when the sub-problem can be separated into multiple independent problems, and when “strong” Benders cuts can be generated. I conjecture that for all UFLNDP problems, both of these are possible. I also introduce the Generalised UFLNDP (GUFLNDP) and discuss how it relates to other UFLNDP problems.
About Statistics, modelling and operations research seminars
Students, staff and visitors to UQ are welcome to attend our regular seminars.
The events are jointly run by our Operations research and Statistics and probability research groups.
The Statistics, modelling and operations research (SMOR) Seminar series seeks to celebrate and disseminate research and developments across the broad spectrum of quantitative sciences. The SMOR series provides a platform for communication of both theoretical and practical developments, as well as interdisciplinary topics relating to applied mathematics and statistics.