J. Gondzio and J.-P. Vial
Abstract
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.