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.