| Chapter
7 Conclusion and future research
[pdf:57kB] [ps:146kB]
This chapter concludes the thesis by highlighting our contributions
in Section 7.1, and then suggesting some potential directions
for future research in shortest path, multicommodity flow
and their related problems in Section 7.2.
Contributions
This thesis contains extensive surveys of both the applications
and solution methods of multicommodity network flow problems.
The previous survey papers in multicommodity network flow
were written more than two decades ago. During the past twenty
years, many new methods and applications in the field have
been proposed and researched. We survey over 200 references
and summarize the applications in Chapter 1, and solution
methods in Chapter 2.
The shortest path problem is a classic combinatorial optimization
problem. It is considered to be easy but is very important
because it appeared as a subproblem in many difficult problems.
For example, solving origin-destination multicommodity network
flow (ODMCNF) problems by the arc-path formulation will usually
require extensive computations of shortest paths between multiple
pairs of nodes.
Although the shortest path problem has been researched for
more than 50 years, to the best of our knowledge, there exist
no combinatorial algorithms designed specifically for solving
multiple pairs shortest path problems (MPSP), until now. In
Chapter 3 we survey over 100 references and summarize most
of the shortest path algorithms in the literature, discuss
their pros and cons, and then demonstrate that a new method
called the Least Squares Primal-Dual method (LSPD), when used
to solve the 1-1 and ALL-1 shortest path problems with nonnegative
arc lengths, performs identical steps to the "classic"
Dijkstra's algorithm. We also discuss the relationship between
LSPD, Dijkstra, and the original primal-dual algorithm in
solving the 1-1 and ALL-1 shortest path problems.
Inspired by an APSP algorithm proposed by Carré <cite>Ca69,
Ca71</cite>, in Chapter 4 we propose two new MPSP algorithms,
called DLU1 and DLU2, which are the first shortest path algorithms
designed specifically for solving multiple pairs shortest
path problems. They do not need to compute a single source
shortest path (SSSP) tree multiple times, nor do they need
to compute all pairs shortest paths (APSP) as many algorithms
in the literature do. In particular, DLU2 can specifically
compute the shortest paths or distances for the requested
OD pairs without wasting time on computing other unrequested
OD entries. Our algorithms are applicable to cases with negative
arc lengths but not negative cycles. Like the Floyd-Warshall
algorithm, our algorithms can also detect negative cycles.
For real world problems where the network topology is fixed
but arc lengths or requested OD pairs are variable, our MPSP
algorithms may take more advantage of similarities than other
shortest path algorithms. In particular, our algorithms rely
on a good node pivot ordering, which can be computed in advance
by many fill-in reducing techniques used for the sparse Gaussian
method in numerical linear algebra. For problems with fixed
topology, this special node ordering needs to be determined
only once, to produce an "ad hoc" efficient shortest
path algorithm that is designed specifically for the problem
topology. This property is advantageous, for problems such
as ODMCNF in which shortest paths between multiple pairs of
OD nodes have to be repeatedly computed for the same network
topology but different arc lengths.
We show correctness and give the theoretical complexity of
our algorithms. Although theoretically both DLU1 and DLU2
have O(n³) time bounds, we expect practical efficiency
because of the fill-in minimizing techniques from numerical
linear algebra.
Chapter 5 gives a detailed introduction to a sparse implementation,
SLU, of Carré's algorithm. We have performed many computational
experiments to compare several implementations of our algorithms
DLU1, DLU2, and SLU, with other 5 label-correcting and 4 label-setting
SSSP shortest path codes <cite>ChGoRa96</cite>
which are considered to be the state-of-the-art. We have done
thorough computational tests on 19 problem families of MPSP
problems, each with 4 different percentages (25%, 50%, 75%,
and 100%) of OD pairs requested. This is the first computational
study in the literature for solving the MPSP problems. Unfortunately,
our proposed algorithms do not perform more efficiently than
most of the state-of-the-art shortest path codes for the cases
we tested. However, it does give evidence that our MPSP algorithms
perform absolutely better than Floyd-Warshall algorithms for
solving MPSP problems. Also, on a real flight network in the
Asia-Pacific region which contains 112 nodes and 1038 arcs,
our new MPSP algorithms do appear to be competitive, and are
even faster than many of the state-of-the-art SSSP codes.
Our MPSP algorithms especially take advantage of problems
where the distribution of OD pairs correspond to a matching
in the OD matrix. That is, our MPSP algorithms perform relatively
better for MPSPs with n requested OD pairs (s_{i},t_{i}) where
each node appears exactly once in both of the origin and destination
sets but not at the same time. In this case, most of the known
shortest path algorithms have to compute shortest paths for
all pairs but our algorithms only compute the necessary shortest
paths rather than solving the APSP problem.
Finally, in Chapter 6 we propose a new primal-dual method
named the "primal-dual key path method" to solve
ODMCNF problems. We describe the details and give two methods
to compute the step length theta^{*}. We also explain how
primal and dual degeneracy may affect our algorithms and propose
perturbation methods to resolve the degenerate pivots and
cycling. In limited computational tests on 17 test problems,
we compare our primal-dual key path method (KEY) with the
generic primal-dual method (PD), Dantzig-Wolf decomposition
method (DW), and the CPLEX LP solver that solves the node-arc
(NA) formulation. We conclude DW to be the most efficient
implementation and give reasons why primal-dual based algorithms
(PD and KEY) may perform worse than DW. Our computational
results also confirm the fact that KEY is more suitable for
cases with many OD commodities. Also, we discover that generating
a single shortest path, rather than all shortest paths, for
each commodity is good enough for the DW method.
Further breakdown of the total running time for PD, KEY and
DW reconfirms the importances of a good MPSP algorithm in
speeding up those path-based algorithms. In particular, up
to 85% total running time of PD, 95% total running time of
KEY and 55% total running time of DW may be spent on shortest
path computations. Thus designing an efficient MPSP algorithm,
as we have researched in Chapter 3, 4, and 5, is very important.
Future research
In this section, we propose some interesting problems for
future research.
Shortest path:
-
Although we have proposed new MPSP
algorithms, in our algorithms, sequence of operations
is based on the node ordering, and does not consider the
affect of individual arc lengths as most SSSP algorithms
do. A good research topic is integration of arc length
into our algorithm. In particular, it may be possible
that some triple-comparisons can be avoided, and such
techniques may speed up our algorithms.
-
In Chapter 5, we chose test problems
based on the computational experiments on SSSP algorithms
by Cherkassky et al. <cite>ChGoRa96</cite>.
Although the computational results are not so encouraging,
it is possible that our MPSP algorithms may perform better
on some specific classes of graphs. Complete graphs, for
example, are a class of networks in which our MPSP algorithms
should run faster than other algorithms not only theoretically,
but also computationally. Note that our algorithms may
have worse performance for larger networks since they
require more memory, and accessing so much memory will
slow down their performance. Hub-and-spoke networks may
also be a class where our algorithms are advantageous
since a careful node ordering which permutes the hub node
and its nearby nodes to larger indices will avoid many
fill-ins.
What classes of graphs may be suitable for our MPSP algorithms?
Why do our algorithms run so quickly for the Aisa-Pacific
flight network? What are the factors that slow down or
speed up our algorithms? Answers to these questions may
lead us to design new and better MPSP algorithms, or help
us to identify appropriate applications for our MPSP algorithms.
-
Theoretically, the running time of
a shortest path algorithm should be proportional to the
total number of triple comparisons. However, due to the
computer architecture, the running time may be "nonlinearly"
affected by the memory caching and accessing which makes
the algebraic algorithms less efficient for larger network.
Another good research is to study the relationship between
the total running time and total number of triple comparisons,
or, to benchmark algorithms using total number of triple
comparisons, instead of using the practical running time.
-
Our MPSP algorithms are inspired by
the Gaussian method applied in a path algebra system.
In other words, computing shortest path distances for
q OD pairs (s_{i},t_{i}) is identical to computing the
q specific entries x_{s_{i}t_{i}} of the matrix X=(I_{n}-C)-1;
where C is the measure matrix and I_{n} is the identity
matrix (see Section 3.4).
Using similar
arguments to the numerical linear algebra, we should be
able to give a "twin" algorithm similar to our
MPSP algorithms which compute q specific entries for some
matrix B?¹ without inverting the whole matrix B (as
does the APSP algorithm), and without computing whole
columns of the matrix that cover the requested OD pairs
(as does by SSSP algorithm). We even do not need to compute
the entries B_{n,j}-1,…,B_{i+1,j}-1
to obtain the entry B_{i,j}-1 (as does by Carré's
algorithm). It remains an open question whether efficiently
computing specific entries for the inverse of a matrix
is difficult in most cases.
-
We have discovered the new Least Squares
Primal-Dual method (LSPD), when used to solve shortest
path problems with nonnegative arc lengths, actually corresponds
to the Dijkstra's algorithm (see Section 3.6). What happens
in the case of negative arc lengths? Will LSPD perform
better than other SSSP algorithms, and in which cases?
In our survey
and computational tests, the LP-based methods such as
primal simplex methods, dual simplex methods, or primal-dual
simplex methods are usually considered to be practically
less efficient than the combinatorial label-setting and
label-correcting methods. LSPD can also be classified
as a LP-based method. Although it has special properties
such as being imperious to degenerate pivots, whether
it will solve MPSP faster or solve SSSP faster for cases
with negative arc lengths require more investigation.
Multicommodity network flow:
-
Our limited computational tests show
that our primal-dual key path method (KEY) is not very
competitive. However, more tests should be done, especially
using the problems with many OD commodities of which KEY
can take more advantage.
-
Both KEY and PD are primal-dual based
algorithms, and perform worse than DW. From our computational
results, we think the key to speeding up KEY and PD lies
in the techniques used to obtain optimal dual solutions
of the RPP. In particular, there usually exist multiple
optimal dual solutions of the RPP. Among these multiple
choices of dual improving directions, which one might
help to reduce the total number of primal-dual iterations?
Which improving direction might reduce the number of degenerate
pivots? If we can reduce the number of primal-dual iterations,
we should save much time in shortest path computations.
The LSPD may
be a good direction to study, since it is also primal-dual
based and can avoid degenerate pivots. More research can
be done in applying LSPD to solve the RPP, either in the
node-arc form or in the arc-path form. The reason we cite
the node-arc form here is because LSPD already has had
success in solving the single commodity min-cost network
flow problem <cite>Go02, BaGoJoSo_1</cite>.
In that case, the node-arc form of the single commodity
problem helps to shorten the time spent in least squares
computations. We suspect similar methods may also be available
for the multicommodity cases. We will continue to investigate
the possibility of applying LSPD in solving the ODMCNF
problems.
-
Some new methods such as the volume
algorithm of Barahona and Anbil <cite>BaAn00</cite>,
as introduced in Section 2.3.2, have not yet been applied
to solve ODMCNF problems. We think it is a good research
direction to try this new algorithm and compare its performance
with other similar algorithms such as bundle methods and
subgradient methods.
-
Although DW has been shown to be very
efficient in our tests, other research in the airline
crew partitioning and cutting-stock problems <cite>HuJo99</cite>
shows that a primal-dual subproblem simplex method might
also be competitive. Since we already develop techniques
for generating all of the shortest paths for our primal-dual
algorithms, it should not be difficult to generate all
of the paths with length within a small threshold value
of the length of shortest paths, as required for the primal-dual
subproblem simplex method to proceed. However, one disadvantage
of this method is the necessity of path index bookkeeping,
as encountered in our PD implementation.
|