n-step cutset inequalities: facets for multi-module capacitated network design problem

Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on links. In network design problems, decisions are made on installation of flow transfer capacities on the links and routing of flow from a set of source nodes to a set of sink nodes through the links. Many network design problems of this type that have been studied involve different types of capacity sizes (modules), which we refer to as the multi-module capacitated network design (MMND) problem. In this paper, we present a new family of inequalities for MMND through polyhedral analysis of a mixed integer set closely related to MMND. We show that various classes of cutset inequalities in the literature are special cases of these inequalities. We also study the strength of this family of inequalities and identify conditions under which they are facet-defining. These inequalities are then tested on MMND problem instances, and our computational results show that this family of inequalities are very effective for solving MMND problems. Generalizations of these inequalities for some variants of MMND are also discussed.

Article

Download

View n-step cutset inequalities: facets for multi-module capacitated network design problem