Auction Algorithms for Shortest Hyperpath Problems.
The auction-reduction algorithm is a strongly polynomial version of the auction method for the shortest path problem. In this paper we extend the  auction-reduction algorithm to different types of shortest hyperpath problems in directed hypergraphs. The results of preliminary computational experiences show that the auction-reduction method is comparable to other known methods for specific  classes of hypergraphs.
Introduction
The shortest hyperpath problem is the extension to directed hypergraphs [11] of the
classical shortest path problem (SPT) in directed graphs. Though not as pervasive
as SPT, shortest hyperpaths have several relevant applications. In particular,
they are at the core of traffic assignment algorithms for transit networks [13, 14, 18].
Shortest hyperpath models have been constructed for the SPT problem in stochastic
and time-dependent networks [17] and for production planning in assembly lines [12].
Moreover, shortest hyperpath algorithms are used as building blocks of enumerative
algorithms for hard combinatorial problems [10]. As a consequence, there is a growing
interest for efficient shortest hyperpath algorithms. This provides motivations
for further investigating known methods [11, 15], both from a theoretical and a
practical point of view, and for developing new ones.
Auction algorithms were first proposed by Bertsekas [1, 2] for the assignment
problem and later extended to general transportation problems [5, 6]. A survey of
the auction algorithms for network optimization problems is contained in [4, Chapter
4]. Auction algorithms for shortest path problems on graphs were proposed in [3].
For the single-origin single-destination case the method can be viewed as an application
of the auction method (with to a specifically constructed assignment
problem, and finite termination of the procedure can be established. Furthermore,
the algorithm is a dual coordinate ascent method. Strongly polynomial version of the
auction method were proposed by Pallottino and Scutell'a [16], who define a pruning
procedure that reduces the graph to the shortest path tree. Further improvements
to this method are given in [7], where the pruning method is strengthened, and the
structure of the reduced graph is exploited to obtain a better time complexity. A
variant of the auction algorithm with pruning is proposed in [8].
In this paper, we devise an auction method for shortest hyperpaths with nonnegative
hyperarc weights, by slightly modifying the SPT algorithm given in [7]. Our
method can be tailored to solve several types of shortest hyperpath problems; for
the various cases, we provide a worst case complexity bound. Finally, we report the
results of a preliminary computational experience.
In Section 2 we give the basic definitions on hypergraphs and shortest hyper-
paths. The proposed auction method for shortest hyperpaths is presented in Section
3. Computational results and conclusions are presented in Sections 4 and 5,
respectively.
Shortest Hyperpaths in Directed Hypergraphs
A directed hypergraph H is a pair (V; E), where V is a set of nodes and E is a set
of directed hyperarcs; a hyperarc is a pair
the tail of e, and h(e) 2 V n T (e) is its head. A detailed introduction to directed
hypergraphs can be found in [11], where a more general definition of hypergraphs is
introduced; the particular class of hypergraphs considered in this paper are called
B-graphs in [11]. The size jej of hyperarc e is the number of nodes it contains in its
tail and head:
The hyperarc e is an arc if 2, and a proper hyperarc if jej ? 2. Denote by m a and
m h the number of arcs and proper hyperarcs,
j. The size of H is the sum of the cardinalities of its hyperarcs:
Given a node u, the Forward Star of u, FS(u), is the set of hyperarcs e such that
and the Backward Star of u, BS(u), is the set of hyperarcs e such that
A path P st , of length q, in the hypergraph E) is a sequence:
st
nodes s and t are
the origin and the destination of the path P st , respectively. We say that node t is
connected to node s in H if a path P st exists in H. If t 2 T (e 1 ), then the path P st
is a cycle. A path is cycle-free if it does not contain any subpath which is a cycle,
Given a hypergraph E) and two nodes s; t 2 V, a hyperpath - st is a
minimal hypergraph (with respect to deletion of nodes and hyperarcs) H
such
2. s;
3. connected to s in H - by a cycle-free path.
Observe that for each there exists a unique hyperarc e 2 E - such that
is the predecessor hyperarc of u in -, and is denoted by e - (u). We say
that node t is hyperconnected to s in H if there exists a hyperpath from s to t in H.
Given a hyperarc a, we say that a hyperarc a r is contained in a, or is a reduction
of a, if h(a r (a). Note that a is contained in itself, and a r
is strictly contained in a if T (a r Given a and u 2 T (a), we denote by anu
the reduction of a obtained deleting u from T (a). We say that a hypergraph is full
when it contains all the possible reductions of each of its proper hyperarcs. A full
hypergraph can be represented by its support hypergraph H s , obtained by deleting
all the strictly contained hyperarcs. Conversely, given any hypergraph H, we can
obtain the corresponding full hypergraph H f by adding all the strictly contained
hyperarcs.
2.1 Shortest Hyperpaths
A weighted hypergraph is such that each hyperarc e is assigned a nonnegative real
weight w(e). The weight of a hyperpath in a weighted hypergraph can be defined in
several ways. It is known that some definitions lead to intractable shortest hyperpath
problems [9]. Here we restrict to definitions that are known to be tractable [11].
A weighting function is a node function that, given a hyperpath - st
assigns a value W - (u) to its nodes, depending on the weights of its hyperarcs. The
value W - (t) is the weight of - under the chosen weighting function. An additive
weighting function satisfies the properties that W -
a function of the predecessor e - (u) only. Formally, an additive weighting function
can be defined by means of the following recursive equations:
where F (e) is a non-decreasing function of the weights of the nodes in T (e). Clearly,
many different additive weighting functions can be defined (see [11]); consider first
the value function, which is obtained by defining F (e) in (1) as follows:
The minimum value (shortest hyperpath) problem consists of finding a set of minimum
value hyperpaths from the origin node s to each node u 6= s hyperconnected
to s. We denote by V (u) the minimum value of a hyperpath - su in H; we assume
if u is not hyperconnected to s.
The distance function is obtained from (1) defining F (e) as follows:
The minimum distance problem asks for the minimum distance hyperpaths from
origin s. Denote by D the vector of minimum distances, where again
if u is not hyperconnected to s.
Since arc weights are nonnegative, the minimum value and minimum distance
problems can be solved efficiently by procedure SBT [11]. A computational analysis
of several variants of SBT can be found in [15].
2.1.1 Minimum Time Problems in Transit Hypergraphs
The problem of finding the passenger's expected travel time is at the core of several
urban transit networks models. This problem has been formulated in terms of hyper-
paths in transit networks [13] and in F-graphs [11, 14]. Here, introducing the time
weighting function in transit hypergraphs, we define a particular shortest hyperpath
problem that, though using a different (and slightly more general) terminology, is
equivalent to the formulations found in [13, 14].
A transit hypergraph is a weighted support hypergraph E) where a
positive parameter OE u is associated with each node u 2 V. Let H
the full hypergraph represented by H. Consider an e contained in a proper
hyperarc a 2 H: the time weighting function is obtained from (1) by defining the
weight w(e) and the function F (e) as follows:
OE u
In practice, F (e) is the weighted average (with weights OE:) of the values W - (\Delta) in
T (e), while w(e) is the inverse of the sum of the weights OE: in T (e). For an arc
corresponding to an arc a 2 E the function F (e) is defined in the
same way, which gives F however, in this case w(e) = w(a) can be any
nonnegative value.
The minimum time problem consists of finding the minimum time hyperpaths,
from a given origin s, in the full hypergraph H f . Note that H f may be considerably
larger than its support H: in practice, solving the minimum time problem efficiently
requires to work directly on H. This is the aim of the following observations.
Denote by E the vector of minimum times, where
is not hyperconnected to s in H f . For each e 2
OE u
Consider a proper hyperarc a 2 E , and let R(a) be the set of the reductions of a;
denote by e(a) the reduction of a yielding the minimum time t(e):
The following relations hold ([13], Proposition 6):
Consider the nodes in T (a) in increasing order of E, i.e. let T
with be the reduction of a such
that T (a g. It follows from (2) that e(a) = a h , where
In practice, working on the support hypergraph requires finding the hyperarc
e(a) without considering the whole set of reductions of a. Indeed, according to the
previous observations, this can be done by processing the nodes in T (a) in the order
. For each u compute the value t(a i
This technique has been used to compute expected
travel times efficiently [13, 14], and will be adopted in our auction algorithm for
the minimum time problem.
2.1.2 Reductions and Shortest Hyperpaths
A hyperarc reduction operation on a proper hyperarc a consists of replacing a by a
hyperarc a r contained in a, returning a reduced hypergraph. Clearly, if the hyper-graph
is weighted, a nonnegative weight w(a r ) must be assigned to a r . The following
propositions show that by suitably choosing the weight on a r a reduction operation
does not modify the optimal solution of the shortest hyperpath problem. Proofs are
rather straightforward and are omitted.
Suppose we are given a weighted hypergraph H, and the corresponding vectors
of optimal solutions V , D for the value and distance weighting functions. Given a
proper hyperarc a and u 2 T (a), consider replacing a by a r = a n u.
Proposition 2.1 If w(a r is the vector of optimal values in the
reduced hypergraph.
Proposition 2.2 If D(u) - is the
vector of optimal distances in the reduced hypergraph.
Now suppose we are given a transit hypergraph H, the corresponding full hypergraph
and the optimum times E. Let e be a proper hyperarc in H f , with t(e) ? E(u)
for each u 2 T (e), and consider replacing e by an arc e
Proposition 2.3 If w(e r is the vector of optimal times in the
reduced full hypergraph.
Auction Algorithms for Shortest Hyperpaths
In this section we propose an auction method for the minimum value problem and
discuss the adaptation to other weighting functions. Before introducing our ap-
proach, we briefly recall some relevant features of the auction algorithms for SPT;
the reader is referred to the cited literature for further details.
The auction algorithm for shortest path problems on graphs maintains a path P
(the candidate path) starting at the origin s and a set of dual node prices p satisfying
the following complementary slackness (CS) conditions:
is the cost of arc (i; j). The algorithm consists of three basic operations:
path extension, path contraction and dual price raise. At each iteration, the candidate
path P is possibly extended, by adding a new node at the end of the path
without violating (3). When no extensions are possible, the dual price of the terminal
node i in P is raised, and if i 6= s the path is contracted by deleting node i. For the
single-origin, single-destination case the algorithm terminates when the destination
node is reached; several variants have been devised, also for the multiple-destination
case.
Consider the case of nonnegative costs and dual prices initially set to zero. At
the first scan of a node i (i.e. when node i becomes the last node in P for the first
time) the optimal distance of node i is determined, indeed, it is equal to p(s). As
a consequence, since p(s) is never decreased during the algorithm, the sequences of
first scan operations ranks the nodes in increasing order of distance from the origin
s. Based on the above property, the auction-reduction method [16] introduces the
following reduction operation: at the first scan of node i, delete each arc entering
i, except the last arc in P . By means of these reduction operations, the graph is
transformed into the shortest path tree, and a strongly polynomial time complexity
can be obtained. Further reduction operations, including deletion of nodes, have
been proposed in [7], improving the complexity bound.
The following observation is at the core of our auction shortest hyperpath method:
Observation 3.1 According to the definition of value, distance, and time weighting
functions, for an arc a = (fug; v) we have F (a)
In other words, the weighting functions above define a standard SPT problem if the
hypergraph is a directed graph. This suggests the following technique:
ffl apply the auction-reduction SPT algorithm to the arcs of the hypergraph;
ffl at the first scan of node i, apply hyperarc reduction operations according to
Properties (2.1),. ,(2.3), possibly generating new arcs.
Note that the hypergraph is modified during the algorithm; each step is applied
to the current hypergraph, as returned by the previous reduction operations. In
practice, during the execution the proper hyperarcs lay in the not yet explored part
of the hypergraph, and they are not considered until they are replaced by arcs as a
result of successive reductions.
Our auction algorithm for the minimum value problem is described in procedure
MinValue. Remark that procedure MinValue applied to a graph becomes the auction
algorithm with graph reduction described in [7].
For each node i, the predecessor pred(i) gives the last arc in the best s-i path
determined so far; for notational convenience, we consider pred(i) as a set; initially,
;. The label l(i) is the minimum s-i hyperpath value determined so far,
which becomes the optimum s-i hyperpath value V (i) at the first scan of node i. We
denote by FSA (i) and FSH (i) the arcs and proper hyperarcs in FS(i), respectively;
thus Replacing hyperarc a by its reduction ani is denoted
by a := an i; note that an i may be an arc. The last node in P is denoted by last(P ).
During the execution of the algorithm, the contained graph is the
directed graph defined by the nodes and arcs in the current hypergraph
Proposition 3.1 At each step of the algorithm, for each node i 2 VA such that
gives the shortest s-i path length in the current contained
graph HA .
Proof: The property follows from the correctness of the auction algorithm for SPT,
observing that a new arc (i; j) is created only before the first scan of node i.
Theorem 3.1 The vector V determined by the algorithm gives the minimum hy-
perpath values in the original hypergraph.
Proof: The theorem can be proved by induction considering nodes in order of first
scan, that is, in increasing order of value V (\Delta). The claim is clearly true at the
beginning because to node s is assigned V Assume that all the previously
assigned V are correct at the first scan of node i. It follows from Proposition 3.1
that l(i) is a lower bound on the length of any path in HA from node s to each
node j such that Therefore, in the current hypergraph, the value of any
hyperpath containing a proper hyperarc cannot be less than l(i). This implies that
is correct; as a consequence, Step 1(c) does not change the optimal
solution (Proposition 2.1).
3.1 Other Weighting Functions
The auction algorithm for minimum value can be easily adapted to the minimum
distance problem. To this aim, it suffices to skip the weight update w(a) := w(a)
V (i) in Step 1(c). This follows from Property (2.2) since, when a is replaced by an i,
for each node j 2 T (a n i). At the end of the algorithm,
the vector of optimal distances. The proof of correctness for the distance function
is similar to the one of Theorem 3.1.
Procedure MinValue(H; s)
for each u 2 V: pred(u) := ;, p(u) := 0, V (u) := l(u) := +1;
steps (a). (d) (first scan of i)
(a) (set value) V (i) := l(i);
(b) (delete
(c) (reduce hyperarcs) for each a 2 FSH (i):
a := a n i, w(a) := w(a)
(d) (update labels, delete arcs) for each a = (i;
otherwise,
deletion, contraction, or expansion)
if FSA
(i)g: go to Step 4;
a=(i;j)2FSA (i)
go to Step 1;
Step 4 (expansion) expand P by node j i , where:
a=(i;j)2FSA (i)
go to Step 1.
The situation is slightly more complex for travel times. Recall that our goal is to
work with the support transit hypergraph, thus we must deal with the corresponding
full hypergraph implicitly. To this aim, we replace hyperarc reductions by arc
insertion operations, as described below.
Consider a proper hyperarc a in the support, with T and
We know that it suffices to consider the k reductions
a (see Section 2.1.1). At the first scan of
node u we compute the value t(a i ); if t(a generate an arc
according to Proposition 2.3. Otherwise, i.e.,
that a i\Gamma1 is the reduction e(a) of a yielding minimum
time, and we delete a. If necessary, a is removed at the first scan of node u k . In
conclusion, for a proper hyperarc a, up to jT (a)j arcs can be generated.
In order to compute each t(a i ) efficiently, for each proper hyperarc a in the
support hypergraph we keep two values, initially set to 0:
u2T (a)
u2T (a)
At first scan of u i , it is t(a We also keep a counter k(a) of visited
nodes in T (a). We rewrite Step 1(c) as follows:
Step 1(c) (reduce hyperarcs) for each a 2 FSH (i):
oe(a)
k(a)
Observe that a new arc is added only if it can be used to improve the label of h(a). In
this case, the current predecessor pred(h(a)) will be deleted in Step 1(d); therefore,
at most one arc generated from a belongs to the contained graph at the end of Step
1.
Lemma 3.1 If the values V (\Delta) assigned before the first scan of node i are correct
then the value V (i) assigned at the first scan of node i is correct.
Proof: Let S be the set of nodes in the current hypergraph whose first scan occurred
before first scan of node i. We know that, for gives the SPT distance
from s in the contained graph; moreover, V (i) is a lower bound on the SPT distance
for each node u 62 S. Consider a proper hyperarc a in the current support hyper-
graph. The reductions of a containing nodes in S only have been already considered
by the algorithm, possibly adding new arcs. Moreover, it is
from (2) that V (i) is a lower bound on t(e(a)). Therefore V (i) is a lower bound
on the minimum time for each node u 62 S in the current hypergraph. The thesis
follows.
Using Lemma 3.1 we can proof the correctness of the auction algorithm for
minimum times by induction, as we did for Theorem 3.1.
3.2 Computational Complexity
The auction-reduction algorithm presented in [7] solves the SPT problem on a graph
E) in O(jV j minfjEj; jV j log jV jg) time. It is easy to see that the maximum
number of arcs generated during the execution of MinValue is m, for the value and
distance weighting functions, and O(size(H)) for the time function. Moreover, the
total time spent in first scans (Step 1) is O(size(H)). Therefore, we can state the
following proposition:
Proposition 3.2 The running time of the auction shortest hyperpaths algorithm is
log ng), for value and distance, while for the time function
it is O(size(H)
Two techniques for improving the running time of the auction-reduction method
are presented in [7]: path scanning ant multipath restructuring. The resulting complexity
is O(jV In fact, the total computation time between two successive
first scan operations is O(jV j), and clearly there are at most jV j first scans. The
above techniques can be easily applied within our shortest hyperpath algorithm; the
next proposition follows:
Proposition 3.3 The auction shortest hyperpath algorithm with path scanning or
multipath restructuring takes O(size(H)+n 2 ) time, for the value, distance, and time
functions.
Computational Results
In this section we present the preliminary computational results for auction methods
for shortest hyperpath problems. Our main goal here is to compare a few variants of
the basic method; a complete experimental evaluation of auction shortest hyperpath
methods would require a much larger effort.
Our basic shortest hyperpath algorithm, denoted by HAR, is an implementation
of procedure MinValue where we used the last data structure [7]. A variant
of this algorithm, denoted by HAR2, makes use of the "second best" device [4,
Chapter 4] too. We implemented a third version, denoted by HARn, where the
"second best" device is not used, and a node contraction operation is introduced.
A node contraction deletes a node k with indegree and outdegree equal to one: the
arcs incident with node k, say (i; are replaced by an arc (i; j), where
contraction operations simplify the current graph,
and may help keeping the current path shorter.
We compared our auction algorithms to an implementation of procedure SBT-
heap [11], denoted by SBTh. All algorithms were coded in C language, and run
on an IBM RISC-6000 P43 workstation, with 64M RAM, using the AIX operating
system.
In general, devising a reasonable experimental setup for shortest hyperpaths is
not a trivial task, since hypergraphs show many more degrees of freedom than graphs
(see e.g. [15]). Here, we restricted ourselves to one weighting function, namely the
distance, and we considered two different hypergraph topologies: random and grid.
Random hypergraphs do not show any special structures, except that the origin
s is a distinguished node, and FS(s) contains only arcs. The size of proper hyperarcs
is chosen randomly in the interval [d min ; d max ]. In our experiments, we set d
and jF and we defined five classes of random hypergraphs with different
values of d a . For proper hyperarcs, and for arcs exiting the
root, weights were generated randomly in the interval [0; 1
for the remaining arcs,
weights belong to [ 1
This choice has been motivated by the attempt to increase
the relevance of hyperarcs.
The results for random hypergraphs are shown in Table 1. For each class, the
value ffi is the expected size of FS(u) for u 6= s. Execution times are given in
milliseconds; each entry is the (rounded) average of 20 instances.
m a 2n 25n 2n 25n 50n
HARn 176 123 135 150 277

Table

1. Random Hypergraphs
In a grid hypergraph nodes are arranged in a b \Theta h grid; a node is identified by its
cohordinates Nodes with the same x cohordinate form a
level; for each pair (x; y) and (x; y 0 ), with y h, there are two vertical arcs
and
. Hyperarcs connect nodes in successive levels; for
each (x; y) with there exists a hyperarc:
h, and y h, In addition, there is an origin node
s, and arcs
s; (1; y)
for each 1 - y - h.
We generated three classes of grid hypergraphs: square, where h, long, where
b AE h, and high, where h AE b. Parameters b and h where choosen in order to have
the same number of nodes in the three classes. Hyperarc weights lay in the interval
vertical arcs weights lay in [1; 2]; weights of arcs leaving s lay in [0; 1
Execution times are reported in Table 2. Each entry is the (rounded) average of
5 instances; times are given in seconds.
high square long
HAR 44 88 86 172 370 785
HARn 44 85 86 176 370 783
SBT 2:22 3:85 1:18 2:06 :65 1:15

Table

2. Grid Hypergraphs
Though clearly incomplete, the above results allow us to draw some conclu-
sions. For what concerns random hypergraphs, our auction algorithms are comparable
to standard label-setting methods, that are the most efficient for this class
of hypergraphs[15]. Auction methods become more and more competitive as the
density increases; in one case, HAR2 gives the best results. On the other hand,
auction methods do not seem to be suitable for large grid hypergraphs. This result
(that matches the computational results for auction methods for long grid graphs)
is not surprising, since the auction algorithm must maintain a long current path P
in order to connect nodes in the last layers.
The "second best" data structure gives the best results for random hypergraphs,
and for high grids, but it is not suitable for square and long grids. Again, this result
is not surprising, since in a grid hypergraph there exist at most two hyperarcs (plus
two vertical arcs) leaving each node; it is conceivable that the good results for high
grids are due to savings obtained when scanning the origin node.
On the contrary, the node contraction operation is almost useless, also for grid
hypergraphs. This result is rather disappointing, since in some preliminary experiments
this operation proved to be very effective on some classes of grid graphs. A
possible explanation may be the following: if a node has the highest distance in the
tail of a hyperarc, it is likely to have the highest distance also in the tail of the other
hyperarc it belongs to; in this case, hyperarc reduction may create two arcs leaving
the node, so that node contraction cannot be applied. This observation may suggest
some guidelines for improving our algorithms.
Conclusions
In this paper, we proposed an auction method for shortest hyperpath problems, that
can be adapted to several types of weighting functions. Our method is derived, with
minor changes, from the auction-reduction SPT algorithm. Indeed, an appealing
feature of our approach is that several techniques originally developed for graphs
could be easily exported to hypergraphs.
From a practical point of view, auction shortest hyperpath methods are comparable
to other known methods, at least in favourable cases. As one would expect,
their behaviour can be dramatically affected by the structure of the underlying hy-
pergraph; however, this seems to resemble closely what happens for graphs.
We can conclude that auction shortest hyperpath methods deserve more inves-
tigation, both on the theoretical and the practical side. A possible direction could
be adapting some of the variants proposed in the literature, such as the price raise
technique devised in [8], and the forward-reverse approach for the single-origin
single-destination case [4, Chapter 4].



--R

A distributed algorithm for the assignment problem.
The auction algorithm: A distributed relaxation method for the assignment problems.
An auction algorithm for shortest paths.
Linear Network Optimization: Algorithms and Codes.
The auction algorithm for the minimum cost network flow problem.
The auction algorithm for transportation problems.
Polynomial auction algorithms for shortest paths.
A modified auction algorithm for the shortest path problem.
Dynamic maintenance of directed hypergraphs.
Max Horn SAT and the minimum cut problem in directed hypergraphs.
Directed hypergraphs and applications.
Hypergraph models and algorithms for the assembly problem.
Equilibrium traffic assignment for large scale transit networks.
Implicit enumeration of hyperpaths in logit models for transit networks.
A computational study of shortest hyperpath algo- rithms
Strongly polynomial auction algorithms for shortest paths.
A hypergraph model for stochastic time dependent shortest paths.
A simplicial decomposition method for the transit equilibrium assignment problem.
--TR
auction algorithms;shortest paths;directed hypergraphs;hyperpaths