Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design

The authors improve the mixed-integer programming formulation of the multicommodity capacitated fixed-charge network design problem by incorporating valid inequalities into a cutting-plane algorithm. The authors use five classes of known valid inequalities: the strong, cover, minimum cardinality, flow cover, and flow pack inequalities. The first class is particularly useful when a disaggregated representation of the commodities is chosen, and the last four are expressed in terms of network cut sets. The authors develop efficient separation and lifting procedures for these classes of inequalities. The authors present computational results on a large set of instances of various characteristics, allowing the authors to measure the impact of the different classes of valid inequalities on the quality of the lower bounds, in particular with respect to the representation of the commodities.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01639267
  • Record Type: Publication
  • Files: TRIS
  • Created Date: May 12 2017 1:28PM