4. SOLUTION APPROACH
The state transition model provides a way to solve
the stashing problem for the steady state by finding
minimum length paths and minimum mean cycles in
the graph. Minimum paths and minimum mean cycles
can be found in polynomial time. Therefore, the
Complexity of the original problem is determined
by the construction of the state transition graph
itself. For this, three major steps are involved:
generating states, finding stashing trees, and generating
transitions. Given that the complexity of the problem
is essentially "hidden" in these three
steps, particular attention has been paid to design
efficient solution procedures.
First, states are generated recursively, rather
than using the more straightforward nested loop
approach. The recursive procedure, shown below,
first identifies the last client in the system then
produces all states for this client. The second-to-last
client is then selected, and generation repeats
until all states are produced.
Procedure Generate-state (i, U)
Multiple line equation(s) can not be represented
in ASCII text.
The second step of the solution, finding the stashing
trees, is probably the most critical. In fact, finding
a simple stashing tree is equivalent to finding
a Steiner tree, which, for general graphs, is an
NP-hard problem. The stashing trees must be generated
so that their costs act as costs for the graph transitions.
There are many exact and heuristic algorithms to
solve the Steiner tree problem (for a survey, see
Winter 1988). We have adapted one of the simplest
algorithms for the special conditions of our problem.
The selected Steiner tree algorithm, due to Hakimi
(1971), consists of finding the minimum spanning
trees on all subgraphs G[subW] of G. G[subW] is
a subgraph made up of a subset W of nodes and of
the arcs incidents (on both extremities) to nodes
belonging to W. Let Z be the subset of nodes that
must be covered by the Steiner tree and N be the
total node set. Then W is defined as Z subset or
is equal to W subset or is equal to N. Note that
the number of subgraphs G[subW] that must be considered
is exponential.
Notation:
D[sub1]: set of clients so that t[subi] = 1, universal
quantifieri is an element of D,
D[sub2]: set of clients so that t[subi] > 1,
universal quantifieri is an element of D,
L: list of stashing trees,
J: set of intermediate nodes,
A[submin]: optimal stashing tree for a particular
set D[sub3],
C[submin]: cost of tree A[submin].
The algorithm Find-trees is as follows:
Procedure Find-trees:
Multiple line equation(s) can not be represented
in ASCII text.
Algorithm Find-trees is composed of two major loops.
The goal of the first loop (steps 1 to 13) is to
find, for all combinations of client nodes in D[sub2],
the combination of intermediate nodes sufficient
to construct a minimum spanning tree. All trees
are added to the list L. The first objective of
the second loop (steps 14 to 21) is to eliminate
the suboptimal trees, that is, trees that are not
Steiner trees for the combination of clients represented.
The second objective of the loop is to implicitly
discard any transitions that can be eliminated,
based on free stashing as shown possible in Theorem
3.
The complexity of the algorithm for searching the
stashing trees is 2[sup|D|+|J|], given by the loop
defined in steps 1 and 3. Note that this complexity
is the same as that of simply applying the Hakimi
algorithm to find the Steiner tree to reach the
nodes belonging to set D[sub1]. Clearly, we have
succeeded in exploiting the special properties of
the problem to create a procedure able to find all
possible Steiner trees with the same complexity
as that required to find one Steiner tree. This
is extremely important, since the number of stashing
trees to be found grows exponentially with the number
of clients in the network.
The final element of the solution is the procedure
to generate reduced transitions.
Procedure Generate-transitions:
Multiple line equation(s) can not be represented
in ASCII text.
Note that list L, created by the procedure Find-trees,
contains only trees corresponding to valid transitions
(considering free stashing) for the reduced graph.
