Interior Point Methods With Decomposition For Linear Programs
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.