COMMODITY FAMILY EXTENDED FORMULATIONS OF UNCAPACITATED FIXED CHARGE NETWORK FLOW PROBLEMS

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 p rogramming relaxations can be obtained by reformulating these problems in terms of an extended variable set corresponding to flow commoditie s for each demand point. In this paper, we develop a theory of reformu lations generalizing to families of commodities defined by arbitrary d emand subsets. In particular, we show how to produce an extended formu lation for any suitable commodity family and isolate simple axioms cha racterizing the families that yield the most useful reformulations. (C ) 1997 John Wiley & Sons, Inc.