Interior-point methods with decomposition for solving large-scale linear programs

This paper deals with an algorithm incorporating the interior-point method into the Dantzig–Wolfe decomposition technique for solving large-scale linear programming problems; the algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.