Commodity family extended formulations of uncapacitated fixed charge network flow problems

Peh H. Ng, Ronald L. Rardin

    Research output: Contribution to journalArticlepeer-review

    1 Scopus citations

    Abstract

    Uncapacitated fixed charge network flow problems are single-commodity flow problems with (positive) fixed charges for opening some arcs and no capacities. Previous research has shown that much improved linear programming relaxations can be obtained by reformulating these problems in terms of an extended variable set corresponding to flow corr modities for each demand point. In this paper, we develop a theory of reformulations generalizing to families of commodities defined by arbitrary demand subsets. In particular, we show how to produce an extended formulation for any suitable commodity family and isolate simple axioms characterizing the families that yield the most useful reformulations.

    Original languageEnglish (US)
    Pages (from-to)57-71
    Number of pages15
    JournalNetworks
    Volume30
    Issue number1
    DOIs
    StatePublished - Aug 1997

    Fingerprint

    Dive into the research topics of 'Commodity family extended formulations of uncapacitated fixed charge network flow problems'. Together they form a unique fingerprint.

    Cite this