Relaxation Method for Large Scale Linear Programming Using Decomposition

We propose a new decomposition method for large-scale linear programming. This method dualizes an (arbitrary) subset of the constraints and then maximizes the resulting dual functional by dual ascent. The ascent directions are chosen from a finite set and are generated by a truncated version of the painted index algorithm of Rockafellar. Central to this method is the novel notion of (ε, δ)-complementary slackness (ε ≥ 0, δ ∈ [0, 1]) which allows each Lagrangian subproblem to be solved only approximately with O(εδ) accuracy and provides a lower bound of Ω(ε(1 − δ)) on the amount of improvement per dual ascent. By dynamically adjusting ε, the subproblems can be solved with increasing accuracy. We show that (i) the method terminates finitely, provided that ε and δ are bounded away from 0 and 1, respectively, (ii) the final solution produced by the method is feasible and is within O(ε) in cost of the optimal cost, and (iii) the final solution produced by the method is optimal for all ε sufficiently small.