Warm Start and -Subgradients in Cutting Plane Scheme for Block-Angular Linear Programs

  • Cahiers de recherche; 1997.23
Publication date1997

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 losse optimality tolerance) and to generate -subgradients. In the decomposition scheme, subproblems are sequentially solved for varying objective functions. It is essential to be eable 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

Citation (ISO format)
GONDZIO, Jacek, VIAL, Jean-Philippe. Warm Start and -Subgradients in Cutting Plane Scheme for Block-Angular Linear Programs. 1997
  • PID : unige:5910

Technical informations

Creation04/15/2010 12:21:10 PM
First validation04/15/2010 12:21:10 PM
Update time03/14/2023 3:27:01 PM
Status update03/14/2023 3:27:01 PM
Last indexation01/15/2024 7:45:57 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack