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

Mervat Chouman (), Teodor Gabriel Crainic () and Bernard Gendron ()
Additional contact information
Mervat Chouman: College of Business, Effat University, Jeddah, Saudi Arabia 21478
Teodor Gabriel Crainic: Département de management et technologie, École des sciences de la gestion, Université du Québec à Montréal, Montréal, Québec H3C 3P8, Canada; and Centre Interuniversitaire de Recherche sur les R�
Bernard Gendron: Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montréal, Québec H3T 1J4, Canada; and Département d’informatique et recherche opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada

Transportation Science, 2017, vol. 51, issue 2, 650-667

Abstract: We improve the mixed-integer programming formulation of the multicommodity capacitated fixed-charge network design problem by incorporating valid inequalities into a cutting-plane algorithm. We 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. We develop efficient separation and lifting procedures for these classes of inequalities. We present computational results on a large set of instances of various characteristics, allowing us 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.

Keywords: multicommodity capacitated fixed-charge network design; commodity representation; cut-set-based inequalities; separation; lifting (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/trsc.2015.0665 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:51:y:2017:i:2:p:650-667

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().