Computational experiments in the formulation of large-scale linear programs - Gerhard Knolmayer (Universität Kiel, Institut für Betriebswirtschaftslehre; ZBW – Leibniz Information Centre for Economics, 1980)
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.
Keywords: 650