Article ID: | iaor20003756 |
Country: | Netherlands |
Volume: | 14 |
Issue: | 1 |
Start Page Number: | 17 |
End Page Number: | 36 |
Publication Date: | Jul 1999 |
Journal: | Computational Optimization and Applications |
Authors: | Vial J.-P., Gondzio J. |
Keywords: | computational analysis |
This paper addresses the issues involved with an interior point-based decomposition applied to the solution of linear programs with a block-angular structure. Unlike classical decomposition schemes that use the simplex method to solve subproblems, the approach presented in this paper employs a primal–dual infeasible interior point method. The above-mentioned algorithm offers a perfect measure of the distance to optimality, which is exploited to terminate the algorithm earlier (with a rather loose optimality tolerance) and to generate ϵ-subgradients. In the decomposition scheme, subproblems are sequentially solved for varying objective functions. It is essential to be able to exploit the optimal solution of the previous problem when solving a subsequent one (with a modified objective). A warm start routine is described that deals with this problem. The proposed approach has been implemented within the context of two optimization codes freely available for research use; the Analytic Center Cutting Plane Method – interior point based decomposition algorithm – and the Higher Order Primal–Dual Method – general purpose interior point LP solver. Computational results are given to illustrate the potential advantages of the approach applied to the solution of very large structured linear programs.