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.

• Record URL:
  https://doi.org/10.1287/trsc.2015.0665
• Record URL:
  http://pubsonline.informs.org/doi/abs/10.1287/trsc.2015.0665
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • Chouman, Mervat
  • Crainic, Teodor Gabriel
  • Gendron, Bernard
• Publication Date: 2017-5

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 650-667
• Serial:
  • Transportation Science
  • Volume: 51
  • Issue Number: 2
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Algorithms; Commodities; Design; Mixed integer programming; Networks
• Uncontrolled Terms: Lifting; Multicommodity capacitated fixed-charge network design; Network design; Separation
• Subject Areas: Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01639267
• Record Type: Publication
• Files: TRIS
• Created Date: Jun 27 2017 4:10PM