An Infeasibility-Pricing Decomposition Method for Linear Programs

This paper presents two versions of a method for solving large linear programs through decomposition. In both versions the problem is decomposed into subprograms as in the Dantzig-Wolfe model, but each version uses a different type of linking program. The subprograms are first solved, and then the infeasibility of the resulting solution for the linking program is used to generate a price-adjustment process (much like a market mechanism), which gradually corrects the objective functions of the subprograms, until either some optimal solutions to the latter yield a feasible solution to the linking program (then the problem is solved), or evidence is obtained that the problem has no feasible solution.