Interior-Point Methods with Decomposition for Solving Large-Scale Linear Programs |
| |
Authors: | Zhao G Y |
| |
Institution: | (1) Department of Mathematics, National University of Singapore, Kent Ridge, Republic of Singapore |
| |
Abstract: | 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. |
| |
Keywords: | Large-scale linear programming interior-point methods Dantzig– Wolfe decomposition algorithmic complexity |
本文献已被 SpringerLink 等数据库收录! |