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

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.