Warm start and epsilon-subgradients in a cutting plane scheme for block-angular linear programs

This paper addresses the issues involved with an interior point-based decom position applied to the solution of linear programs with a block-angular st ructure. Unlike classical decomposition schemes that use the simplex method to solve subproblems, the approach presented in this paper employs a prima l-dual infeasible interior point method. The above-mentioned algorithm offe rs a perfect measure of the distance to optimality, which is exploited to t erminate the algorithm earlier (with a rather loose optimality tolerance) a nd to generate epsilon-subgradients. In the decomposition scheme, subproble ms are sequentially solved for varying objective functions. It is essential to be able to exploit the optimal solution of the previous problem when so lving a subsequent one (with a modified objective). A warm start routine is described that deals with this problem. The proposed approach has been imp lemented within the context of two optimization codes freely available for research use: the Analytic Center Cutting Plane Method (ACCPM)-interior poi nt based decomposition algorithm and the Higher Order Primal-Dual Method (H OPDM)-general purpose interior point LP solver. Computational results are g iven to illustrate the potential advantages of the approach applied to the solution of very large structured linear programs.