An Algorithmic and Numerical Comparison of Several Interior-Point Methods

Vanderbei, R. J., Duarte, A. and Yang, B.

We present a unified framework for studying interior point methods for linear programming. Within this framework, we compare three fundamental methods: (1) path-following, (2) barrier, and (3) primal/dual affine-scaling (our terminology differs slightly from the commonly accepted terminology). The step directions for each of these methods are linear combinations of three fundamental directions: (1) step-toward-optimality, (2) step-toward-center, and (3) step-toward- feasibilty. By making very simple modifications to LOQO, we have created efficient implementations of each of these methods, which we compared one to another. We shall present the results of this comparison. In addition, associated with each of the three fundamental algorithms, there are three choices for how to organize the system of equations that must be solved: (1) general ordering heuristics applied to the KKT system, (2) primal-scaling, and (3) dual-scaling. Each of these three choices produce identical step directions but the choice can have a dramatic effect on the efficiency of the implementation.

Contact the first author at rvdb@princeton.edu


 [IP PAGE]  [SEARCH AGAIN]