Relaxation method for large scale linear programming using decomposition

The paper proposes 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. The paper shows 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.