Warm Start and Epsilon-subgradients in the Cutting Plane Scheme for Block-angular Linear Programs

Logilab Technical Report 1997.1

J. Gondzio and J.-P. Vial

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 $\epsilon$-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 (ACCPM) - interior point based decomposition algorithm and the Higher Order Primal-Dual Method (HOPDM ) - 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.

Key words: Decomposition, Cutting Plane Methods, Interior Point Methods, Warm Start, Block-Angular Linear Programs.

PDF TR1997.1.pdf.
Written: June 1997, revised November 1997.
Published: Computational Optimization and Applications 14(1999) 17-36.