2 Solution methods for multicommodity network flow problems
In this chapter, we try to summarize most of the solution
techniques that have appeared in the literature, especially
those which appeared after 1980.
Due to the special block-angular structure of MCNF problems,
many special solution methods have been suggested in the literature.
Basis partitioining methods partition the basis in a way such
that computing the inverse of the basis is faster. Resource-directive
methods seek optimal capacity allocations for commodities.
Price-directive methods try to find the optimal penalty prices
(dual variables) for violations of the bundle constraints.
Primal-dual methods raise the dual objective while maintaining
complementary slackness conditions and will be discussed in
more detail in Chapter 6. In the last two decades, many new
methods such as approximation methods, interior-point methods
and their parallelization have been proposed. Although the
convex or integral MCNF problems are not the main interests
of this dissertation, we still summarize recent progress in
We have introduced
and summarized most of the methods in the literature for solving
the MCNF problems. Different solution techniques may be advantageous
for different MCNF problems depending on the problem characteristics.
This dissertation focuses on solving the class of MCNF problems
in which many OD commodities have to be routed. Therefore,
the algorithms by Barnhart et al. <cite>BaJoHaSi95,
BaHaVa96, BaHaVa00</cite> seem to be most suitable for
our purpose. In Chapter 6, we will propose new primal-dual
column generation algorithms which follow the PD algorithmic
framework. We will also exploit the ideas from the CYCLE-RELAX
In our algorithms (see Chapter 6), subproblems which seek
shortest paths between multiple pairs must be repeatedly solved.
Therefore, efficient multiple pairs shortest paths (MPSP)
algorithms will speed up the overall computational efficiency
of our MCNF algorithms. We introduce several shortest path
algorithms in Chapter 3, give our own new MPSP algorithms
in Chapter 4, and describe their computational performance
in Chapter 5. We will introduce our MCNF algorithms and their
computational performance in Chapter 6.