VALID INEQUALITIES AND PROJECTING THE MULTICOMMODITY EXTENDED FORMULATION FOR INCAPACITATED FIXED CHARGE NETWORK FLOW PROBLEMS

Multicommodity extended formulations of single source uncapacitated fi xed charge network flow problems have significantly sharper linear pro gramming relaxations than the standard flow formulations. However the tradeoff is the introduction of many new constraints and variables to accomodate a sink-oriented flow disaggregation. In this paper we intro duce a new family of dicut collection inequalities and show that they completely describe the projection of the multicommodity formulation o nto the original variables. A simple subclass is seen to include a var iety of known inequalities for particular models, and combinatorial se paration is examined for some special cases.