Facility Location: A Guide to Modeling and Solving Complex Problem Variants via Lagrangian Relaxation Heuristics

Facility Location problems fit a large variety of practical planning contexts and are among the most studied combinatorial optimization problems. While these problems may become quite complex in certain applications, they are particularly well tackled by mathematical decomposition via Lagrangian Relaxation. This chapter provides a guide to modeling and solving a variety of complex single-echelon facility location problem via Lagrangian Relaxation heuristics. It first reviews the problem variants successfully tackled by Lagrangian Relaxation. It then guides the development of strong mixed-integer programming formulations for a variety of problem variants, covering multi-period models, a wide range of capacity constraints, modular facility structures, facility relocation, and parameter uncertainty. Finally, it discusses how such variants can be efficiently solved via Lagrangian Relaxation, capable of providing tight lower and upper bounds in short computing times.