A Decomposition Algorithm for Linear Programming Problems

with Block Angular Constraints

Li   Wu


A decomposition algorithm for solving linear programming problems with block angular constraints is given in this paper. Based on the decomposition principle for linear programming problems by the interior point method, the original problem can be transformed into a sequence of subproblems and a master problem problem associated with every subproblem, and the algorithm approaches to an optimal solution of the problem with through the feasible region, without searching the vertices from one to another along the edges. In order to save the storage, the sparse matrix technique is used for the implementation, and numerical results demonstrate the efficiency of the algorithm for a group of test problems.