On scaling linear programs-Some experimental results

The paper considers the possibility of preprocessing linear programs by row and column scaling in order to reduce the number of simplex iterations required for solving the programs when Dantzig’s original entering variable rule is used. It is conjectured that an appropriate scaling objective should be to try to give all nonzero coefficients of the linear program the same magnitude. This objective is quantified by the introduction of different optimal scaling models. Optimality conditions are derived for each model, and based on these a number of scaling methods are developed. The scaling methods have been applied to two classes of small-size randomly generated linear programs, one dense class and one sparse. The results of these experiments are promising, and motivate further research in this direction.