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

Abstract

This paper deals with an algorithm incorporating the interior-point method into the Dantszig-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.