Given a directed graph, G = (V,A) (see Bondy and Murty [2], and West [9]), the uncapacitated fixed charge network flow problem, (UF), is the following mixed-integer program
where is the single source vertex for
all flow, is a collection of
sink vertices with rational demand ,
denotes the flow in arc at
variable cost .
Arcs of also carry fixed cost with
indicating that arc (i,j) is selected.
In general we assume that all costs are nonnegative.
Figure 1(a) shows a simple instance.
The (UF) model is an important one in discrete optimization because a wide variety of applied problems can be effectively modeled as uncapacitated fixed charge network flow problems. These problems include lot-sizing (planning production setups) problems, designing single commodity utility and logistics networks, and planning for warehouse and distribution systems.
Problem (UF) is NP-Hard for because it contains as a special case the hard Steiner Tree Problem (Garey and Johnson [4]). (There are polynomial algorithms for . We denote by the linear programming relaxation of any problem (P) and by its optimal value.) Thus, one way of obtaining approximate (UF) solutions is by solving its linear programming relaxation, and rounding ``up'' to one all fractional in the relaxation optimum. Unfortunately, that LP-relaxation usually provides a weak approximation to its corresponding discrete problem, i.e. often . For example, Figures 1 (b) and (e) show versus .
Now, we present an approach to obtain better LP-relaxation values as approximations to .
A well known structural description of the optimal solutions in the directed graph associated with (UF) can be stated as follows:
Thus there is no loss of generality in thinking of the flow in any arc in terms of the sinks for which it is bound. We will term solutions conforming to Remark 1 as extreme.
This observation led Rardin and Choe [7] to propose the multicommodity extended formulation, (MCE), which is obtained from (UF) by artificially extending the single commodity in (UF) to multiple commodity networks, one for each sink t. New variables, , represent the fraction of flow destined for sink t passing through arc (i,j).
It is easy to see is optimal in (UF) if and only
if there are w's so that is optimal in (MCE).
The point of this extended formulation is to make optimal values
of the y variables in LP-relaxations more
accurately reflect their integer values.
In each optimal will equal the fraction of
total demand passing through arc (i,j).
In , will equal the maximum of the
fraction of particular demands satisfied through arc (i,j).
For example in Figure 
(b) in
because only 2/5 of total demand passes through
arc (1,2).
Corresponding results in Figure (c) have
,
the maximum of and .
These tighter constraints on y-variables produce a
relaxation optimal value of versus
.
Computational testing
(see for example Balakrishnan, Magnanti and Wong [1])
confirms that values are usually much
sharper (closer to the solution value of
the discrete model) than those of .
However, need not be exact (e.g. in Figure ),
and there are instances in which there is a relatively
large gap between and
.
We investigate new commodity family extended
formulations (CFE) that seek to improve on .
(See Ng and Rardin [6]).
This approach is to introduce a family 
of commodity variables
Using these notions we are finally ready to
develop a rudimentary statement of the commodity family
extended formulation associated with a given commodity family
and representation function 
.
Constraints () assume flow originates at source s
for all commodities , the representation of the
whole sink set.
Demands are fulfilled at by singleton commodities
.
If contains more than those singleton I, this implies
flows must split along
the way from source to sink into commodities for
smaller and smaller demand subsets.
Variables in the above formulation provide the required commodity interfaces. In particular,
Each is a subset of T, so that the multicommodity model (MCE) is the special case where .
Figure (d) shows the result is an LP-relaxation
strictly improving on .
(The formulations of (CFE) and its relaxations are in the
next section.)
For this example, the stronger (CFE) form achieves
integer optimal value .
Clearly not all subsets of T can be included in the
of any practical (CFE) because their number
grows exponentially with |T|.
Still, there are an enormous variety of incomplete
's of manageable size.
Ng and Rardin [6]
described some properties of ``good'' families,
most of which are trivial in the (MCE) setting but subtle and complex
in richer commodity families.
They also characterized which families should be considered.
For each such family, they derived
elegant axioms characterizing when a
possesses the desired property.
