An Artificial-Variable Elimination Method for Solving Block-Diagonal Programming Problems

The algorithms of this paper solve problems of the “decomposition” structure. It presents the basic framework for a class of algorithms, along with two possible versions. The basic algorithm generates a sequence of solutions that satisfy complementary slackness with a sequence of dual feasible solutions such that, when the linking constraints are satisfied, an optimum is obtained. Computational experience is reported for the first version in comparison with RSMFOR, a simplex program, on randomly generated problems and a three-period refinery model. Using the number of nonzero multiplications as the basis for comparison, the results show the first version substantially better than the simplex method. The computational experience is discussed at some length.