On the effectiveness of the linear programming relaxation of the 0-1 multi-commodity minimum cost network flow problem

Dae Sik Choi, In Chan Choi

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    3 Citations (Scopus)

    Abstract

    Several studies have reported that the linear program relaxation of integer multi-commodity network flow problems often provides integer optimal solutions. We explore this phenomenon with a 0-1 multi-commodity network with mutual arc capacity constraints. Characteristics of basic solutions in the linear programming relaxation problem of the 0-1 multi-commodity problem are identified. Specifically, necessary conditions for a linear programming relaxation to have a non-integer solution are presented. Based on the observed characteristics, a simple illustrative example problem is constructed to show that its LP relaxation problem has integer optimal solutions with a relatively high probability. Furthermore, to investigate whether or not and under what conditions this tendency applies to large-sized problems, we have carried out computational experiments by using randomly generated problem instances. The results of our computational experiment indicate that there exists a narrow band of arc density in which the 0-1 multi-commodity problems possess no integer optimal solutions.

    Original languageEnglish
    Title of host publicationComputing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings
    PublisherSpringer Verlag
    Pages517-526
    Number of pages10
    ISBN (Print)3540369252, 9783540369257
    Publication statusPublished - 2006
    Event12th Annual International Conference on Computing and Combinatorics, COCOON 2006 - Taipei, Taiwan, Province of China
    Duration: 2006 Aug 152006 Aug 18

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4112 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other12th Annual International Conference on Computing and Combinatorics, COCOON 2006
    Country/TerritoryTaiwan, Province of China
    CityTaipei
    Period06/8/1506/8/18

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'On the effectiveness of the linear programming relaxation of the 0-1 multi-commodity minimum cost network flow problem'. Together they form a unique fingerprint.

    Cite this