Chapter 2 Solution methods for multicommodity network flow problems

[pdf:170kB] [ps:366kB]

        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 these topics.

Summary

        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 algorithm.

        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.