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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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



    Published in:

    Publication date :

    2017




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



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

    Chouman, Mervat / Crainic, Teodor Gabriel / Gendron, Bernard | British Library Online Contents | 2017



    Multicommodity vs. Single-Commodity Routing

    Archetti, Claudia / Campbell, Ann Melissa / Speranza, M. Grazia | British Library Online Contents | 2016


    Multicommodity vs. Single-Commodity Routing

    Archetti, Claudia | Online Contents | 2016