Computational experiments in the formulation of large-scale linear programs

One of the decisions in the construction of linear programs is upon the formulation which should be used. This paper explains why there is usually a very large number of equivalent formulations and reports on the computational behavior of these formulations. The usual textbook-hypothesis which Claims that CPU-time increases with the cube of the number of constraints is falsified; it is shown that the advantage of reducing the number of rows may be overcompensated by an increase in the number of nonzeros.