Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
type: Item
instance of: scholarly article
title: Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
zbMATH Open document ID: 0807.90051
DOI: 10.1016/0377-2217(93)90263-M
author: Ronald L. Rardin
author: Laurence A. Wolsey
published in: European Journal of Operational Research
publication date: 1994-05-05T00:00:00Z
review text: 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.
reviewed by: Peter Brucker
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C11
zbMATH DE Number: 550246
zbMATH Keywords: multicommodity extended formulation
zbMATH Keywords: lot sizing
zbMATH Keywords: uncapacitated fixed charge networks flow problem
zbMATH Keywords: linear inequalities
MaRDI profile type: Publication
cites work: Packing and covering a tree by subtrees
cites work: Uncapacitated lot-sizing: The convex hull of solutions
cites work: A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs
cites work: Using separation algorithms to generate mixed integer model reformulations
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: Lot-size models with backlogging: Strong reformulations and cutting planes
cites work: Polyhedral Characterization of the Economic Lot-Sizing Problem with Start-Up Costs
cites work: Valid inequalities and separation for uncapacitated fixed charge networks
cites work: Solving Mixed Integer Programming Problems Using Automatic Reformulation
cites work: Uncapacitated Lot-Sizing Problems with Start-Up Costs
full work available at URL: 0377-2217(93)90263-m
OpenAlex ID: W2039342074
Recommended article: Q4355486
Recommended article: Valid inequalities and separation for capacitated fixed charge flow problems
Recommended article: Valid inequalities and separation for uncapacitated fixed charge networks
Recommended article: Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem
Recommended article: Solving to optimality the uncapacitated fixed-charge network flow problem
Recommended article: New partial aggregations for multicommodity network flow problems: an application to the fixed-charge network design problem
Recommended article: Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design
Recommended article: Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design
Recommended article: Approximate solutions of capacitated fixed-charge minimum cost network flow problems
Recommended article: Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach
description: scientific article; zbMATH DE number 550246