Commodity family extended formulations of uncapacitated fixed charge network flow problems

Commodity family extended formulations of uncapacitated fixed charge network flow problems

0.00 Avg rating0 Votes
Article ID: iaor20021961
Country: United States
Volume: 30
Issue: 1
Start Page Number: 57
End Page Number: 71
Publication Date: Aug 1997
Journal: Networks
Authors: ,
Abstract:

Uncapacitated fixed charge network flow problems are single-commodity flow problems with (positive) fixed charges for opening some arcs and no capacities. Previous research has shown that much improved linear programming relaxations can be obtained by reformulating these problems in terms of an extended varible set corresponding to flow commodities for each demand point. In this paper, we develop a theory of reformulations generalizing to families of commodities defined by arbitrary demand subsets. In particular, we show how to produce an extended formulation for any suitable commodity family and isolate simple axioms characterizing the families that yield the most useful reformulations.

Reviews

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