# 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, and colleagues in the Centre for Applications in Natural Resource Mathematics.

Seminars are usually held on Tuesdays from 11am to 12pm.

#### Information for speakers

Plan to speak for up to 40 minutes, and allow up to 15 minutes for questions and discussion.

Pitch your presentation to an interdisciplinary mathematical audience.

To avoid technical delays on the day, contact us a few days in advance of your presentation to discuss requirements.

You can either email us your presentation in advance, or save it to a memory stick. Microsoft PowerPoint presentations and PDFs are the most convenient file formats, but you can also run the talk from your own laptop.