Optimization Online


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

Haochen Luo (hcluo***at***tamu.edu)
Kiavash Kianfar (kianfar***at***tamu.edu)

Abstract: Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on arcs. Many network design problems of this type that have been studied involve different types of capacity sizes (modules), and we call them multi-module capacitated network design (MMND) problem. In this paper, we introduce a new family of inequalities for MMND by studying a mixed integer set, the cutset polyhedron, which is closely related to MMND. We show that various classes of cutset inequalities in the literature are special cases of these inequalities. We also show the strength of this family of inequalities by showing they are facet-defining under certain conditions. Our computational results show that these classes of inequalities are very effective for solving MMND problems. Generalizations of these inequalities for some variants of MMND are also discussed.

Keywords: n-step cutset inequalities; multi-module capacitated network design; cutset polyhedron; n-step MIR; telecommunication

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Applications -- Science and Engineering (Facility Planning and Design )


Download: [PDF]

Entry Submitted: 11/02/2018
Entry Accepted: 11/02/2018
Entry Last Modified: 05/08/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society