Interior Point Methods With Decomposition For Linear Programs

Gongyun Zhao

This paper deals with an algorithm which incorporates the interior point method into the Dantzig-Wolfe decomposition technique for solving large-scale linear programming problems. At each iteration, the algorithm performs one step of Newton's method to solve a subproblem, obtaining an approximate solution, which is then used to compute an approximate Newton direction to find a new vector of the Lagrange multipliers. We show that the algorithm is globally convergent and has the polynomial-time complexity.

Research Report No. 686, Department of Mathematics, National University of Singapore, Singapore, 1996.