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

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

0.00 Avg rating0 Votes
Article ID: iaor20171666
Volume: 51
Issue: 2
Start Page Number: 650
End Page Number: 667
Publication Date: May 2017
Journal: Transportation Science
Authors: , ,
Keywords: heuristics, networks, design
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.

Reviews

Required fields are marked *. Your email address will not be published.