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

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

0.00 Avg rating0 Votes
Article ID: iaor19971019
Country: Netherlands
Volume: 71
Issue: 1
Start Page Number: 95
End Page Number: 109
Publication Date: Nov 1993
Journal: European Journal of Operational Research
Authors: ,
Keywords: inventory: order policies
Abstract:

Multicommodity extended formulations of single source uncapacitated fixed charge network flow problems have significantly sharper linear programming 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 the authors introduce a new family of dicut collection inequalities and show that they completely describe the projection of the multicommodity formulation onto the original variables. A simple subclass is seen to include a variety of known inequalities for particular models, and combinatorial separation is examined for some special cases.

Reviews

Required fields are marked *. Your email address will not be published.