DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 00, 0000

A Fast Implementation of a Path-Following Algorithm for Maximizing a Linear Function Over A Network Polytope ANIL JOSHI, ARTHUR S. GOLDSTEIN, AND PRAVIN M. VAIDYA December 31, 1992 1. Introduction Many network optimization problems - Assignment, Maximum Flow, and Minimum Cost Flow - can be cast as Linear Programming (LP) problems. Recently several algorithms have been proposed for LP which belong to the general class of algorithms known as Interior Point methods (See [Vai90, Vai89, Ren88, Kar84]). The objective of our implementation is to show that pathfollowing interior point algorithms can work well if the problem peculiarities are taken into consideration and appropriate data-structures are chosen. Computational experiments comparing the performance of Network Simplex and Interior Point methods have been carried out by several researchers. The results can be found in [AM91, KY91, RV90, Raj89, A^{+}85].

We use the notation e for the number of edges and v for the number of vertices in the given network. A network flow problem is defined as the following LP [FF62].

max c^{T} x

subject to the lower and upper bound (i.e. capacity) constraints

l_{i} ≤ x_{i} ≤ u_{i}

and the flow conservation constraints

Ax = b
\begin{matrix}c \\ ◯ \end{matrix}0000 American Mathematical Society

0000-0000/00 $1.00 + $.25 per page

1

1991 Mathematics Subject Classification. Primary 90B10, 90C05, 90-04; Secondary 49M35, 65K05.