Review of valid inequalities pertinent to network design problems

The objective of this paper is to present a survey of relevant valid inequalities for the multicommodity capacitated fixed-charge network design problem. We present first a review of the relevant literature on relaxations and heuristic approaches. We observe that these approaches alone are not sufficient to solve large-scale instances of the problem. However, a combination of these approaches and polyhedral methods appears very promising. Then, we present three classes of relevant valid inequalities for the problem that have been studied for related problems. We present as well experimental results on the general implementations of some of these inequalities in a state-of-the-art commercial software. These experiments point towards the necessity of profound polyhedral studies in order to solve efficiently large-scale instances of the problem.