**Chapter
6 Primal-dual column generation and partitioning methods**
[pdf:240kB] [ps:617kB]
We have briefly introduced the primal-dual methods in Section
2.4 and key variable decomposition in Section 2.3.3. In this
chapter, we will combine these two methods to solve MCNF problems.
**Summary**
In this chapter
we first discussed generic primal-dual methods (PD) for solving
origin-destination multicommodity network flow (ODMCNF) problems.
We proposed two methods to determine the step length theta^{*}
and choose the latter one for our implementation. We perturbed
the objective coefficients of the artificial variables to
resolve the degenerate pivots caused by primal degeneracy.
We then proposed a new method, the primal-dual key path method
(KEY), to solve ODMCNF problems. We discussed its properties
and difficulties, and proposed techniques to resolve cycling
problems caused by dual degeneracy.
We compared our algorithm KEY with other three algorithms,
PD, DW, and NA. We found DW, the Dantzig-Wolfe decomposition
method, was the fastest algorithm in all of our tests. As
expected, solving the node-arc formulation (NA) without any
special techniques such as resource-directive methods or the
basis-partitioning methods introduced in Chapter 2, will be
time-consuming and very inefficient, except for small networks.
KEY follows the generic PD steps but uses the key path decomposition
method to solve a relaxed RPP at each iteration. It is designed
for problems with large number of commodities. In our limited
tests, KEY does perform better than PD for cases with more
commodities. However, for larger cases with few commodities,
it performs much worse than PD. The reason for its inefficiency
is that it requires many iterations of key path swapping operations.
Although our proposed technique, which perturbs the objective
coefficients for path flows, has reduced the chances of key
path swapping and resolved the cycling problem caused by dual
degeneracy, it is still not efficient enough for some larger
cases.
More tests should be performed, especially using cases with
a large number of commodities, to draw more solid conclusions
on the efficiency of KEY.
We also found that generating all shortest paths for the same
commodity may not save time in Dantzig-Wolfe decomposition
with a column generation scheme. That is, generating a single
shortest path for each commodity is good enough.
To explain why DW performs so well compared to PD and KEY,
we give the following reasons:
First, DW generates fewer shortest paths
than DW and KEY. In particular, DW will not generate a path
twice, if we keep all of the previously generated paths
in the restricted master problem. PD and KEY, on the other
hand, generate a new set of all shortest paths at every
iteration using the new dual solutions. Note that between
two primal-dual iterations, many paths may remain the shortest
and do not need to be altered. The reason that we remove
the entire previous set of shortest paths and add a new
set of shortest paths is that keeping old paths would require
bookkeeping on each specific path, which is difficult and
inefficient. In particular, to check whether a path is in
the current set takes exponential time when there are (exponentially)
many paths to be added or removed. Furthermore, using CPLEX
to solve the RPP usually requires the sparse representation
of the constraint matrix. In this case, each path corresponds
to a column. Removing and adding columns will require a
new sparse representation. Although we can add easily columns
at the end of the matrix, identifying the columns to be
removed requires sparse matrix operations. Thus, PD and
KEY invoke many more operations than DW does, making the
algorithms less efficient.
Degeneracy is an important issue, especially for primal-dual
based methods like PD and KEY. Multiple optimal dual or primal
solutions may cause implementation problems. Techniques that
choose a "good" optimal solution are desired, and
may drastically shorten the total running time.
KEY has one more issue of concern than PD: the memory requirement.
To implement the key path swapping operations more efficiently,
we allocate memory to store the initial relaxed RPP at each
primal-dual iteration. Inside a primal-dual iteration, KEY
may perform many iterations of key path swapping. The column
corresponding to the key path is empty, and an empty column
has no sparse representation at all. Thus, it is clumsy to
do the key path swapping and column operations only using
the original sparse representation of the RPP. Although we
have an efficient way to swap key paths and update each column
for the commodities that have new key paths, it still requires
much time, especially when there are many iterations of key
path swapping operations. Table 3.3 and Table 3.4 show that
more iterations of swapping key paths results in a longer
running time compared to PD.
To make KEY more competitive, new techniques that identify
better dual improving directions can be developed. Our results
show that efficient MPSP algorithms play a crucial role in
improving all of the path-oriented multicommodity network
flow algorithms, especially primal-dual based algorithms like
PD and KEY which 85% (PD) or 95% (KEY) of their total running
time computing shortest paths. |