A Two-Phase Decomposition Algorithm for Linear Programs with Angular Structure

Abstract

Large scale linear programming problems often have special forms of constraints. An angular structure is a typical instance. The Dantzig-Wolfe decomposition principle is an effective tool for solving the linear programming problem with angular structure. So far, the decomposition principle has been used only in the second-phase problem of the two-phase simplex procedure. This paper proposes a complete two-phase algorithm, in which the decomposition technique is fully utilized both in the first and the second phases. The present algorithm is then applicable, without any a priori knowledge of an initial feasible solution, to all the classes of linear programs with angular structure, though it may have some computational redundancies.