Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems (Q1319550)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
scientific article

    Statements

    Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems (English)
    0 references
    0 references
    0 references
    5 May 1994
    0 references
    Two mixed integer programming formulations for the uncapacitated fixed charge network flow problem are discussed. While the first formulation is a standard one the second is a multicommodity extended formulation. The second formulation provides much better bounds via its LP-relaxation. What limits its effectiveness as a solution tool is the high number of additional variables and constraints. A new class of linear inequalities is proposed which has the property that, when added to the first formulation, the new system of inequalities describes the projection of the multicommodity extended formulation onto the space defined by its continuous variables.
    0 references
    0 references
    0 references
    multicommodity extended formulation
    0 references
    lot sizing
    0 references
    uncapacitated fixed charge networks flow problem
    0 references
    linear inequalities
    0 references
    0 references