An example is shown below with
symmetric random data. One additional parameter is required
for this model and is placed in cell F4. This is an exponent
(Exp.) that will be used in the objective function. For a minimization
problem the exponent will be between 0 and 1, inclusive.
The form constructed by the Optimize add-in for this
problem is shown below. Several new rows appear in the form
for a flow tree. The coefficients for the arcs are placed in
the table starting in row 14. Row 8 holds the node flows and
row 9 holds the arc flows. The node flows are data items which
for simplicity we make all 1's for the example. In general the
node flows should be nonnegative numbers. The value of p
is in F4, and it is 0.5. This is equivalent to multiplying the
coefficient by the square root of the flow.
To explain the problem we use the solution shown in row 7.
Recall that the value of a variable tells the node that originates
the arc that enters a particular node. For example x2=5 implies
that arc (5, 2) is part of the tree. The initial tree is illustrated
in the figure below. The node flows are shown in square brackets
on the figure and the arc flows are in parentheses. The node
flows may be viewed as demands for some material at the nodes.
The tree arcs are to deliver the demanded quantities and the
materials enter the network at the root node (node 1). The flow
in the tree arcs are determined by conservation of flow. For
example, since the arc (2, 3) serves only node 3, the flow on
this arc is 1. Arc (5, 2) serves nodes 2, 3 and 7, so it must
carry 3 units of flow.
Given the tree designation in row 7 on the worksheet,
the arc flows are computed in row 9 by Excel formulas. Row 10
holds the unit costs for the arcs selected for the tree. Row
11 computes the product of the unit cost multiplied by the arc
flow raised to the power of the exponent. The sum of the values
in row 11 is in cell D3 and is the objective to be minimized.
When the exponent is strictly between 0 and 1
and the coefficients are positive, the objective is a concave
function of flow. This kind of problem is difficult because
the associated math programming model has multiple local minima.
For the math programming model, every tree is a basic solution
and every basic solution may be a local minimum. Thus the flow
problem for exponents strictly between 0 and 1 is hard
and must be solved by combinatorial methods.
We use exhaustive enumeration for the example
problem and the optimum solution is shown below.
The optimal tree is shown in the graphic.