Exact Methods for Fixed-Charge Network Design

This chapter is dedicated to exact algorithms for single-commodity and multicommodity fixed-charge network design. These problems are notoriously difficult, since they are in general strongly N P $$\mathcal {N}\mathcal {P}$$ -hard. In addition, their objective function includes both fixed design costs and variable transportation costs, which results in complex tradeoffs that complicate the task of finding optimal solutions. Multicommodity capacitated fixed-charge problems are particularly challenging, since even their LP relaxations are difficult to solve, as they are often highly degenerate. In addition, the formulations of these problems display a large number of both variables and constraints. In this context, decomposition methods that exploit subproblem structures are useful to seek optimal solutions for such problems. This chapter is divided into three parts. Part I presents relaxations that can improve the quality of the lower bounds, while exploiting the subproblem structures. Part II focuses on enumeration algorithms that use the modeling techniques covered in Part I. Part III is dedicated to the solution of large-scale instances by combining the advanced enumeration algorithms of Part II with heuristic methods and by exploiting parallel computing.