Simplex-Algorithm

The Netlib repository is a collection of “freely available software, documents, and databases of interest to the numerical, scientific computing, and other communities” that is maintained by AT&T Bell Laboratories, the University of Tennessee, and Oak Ridge National Laboratory(http://www.netlib.org). A set of LP test problems of linear programs, which is known as the Netlib LP database, is available on http://www.netlib.org/lp, a web site by David M. Gay.

Consise solutions to the Netlib LP problems are given by Koch (2004).

In the following, some of the linear programs of the Netlib LP database are given. Please refer to the Netlib repository for further problems.

Afiro is a rather simple problem with 32 variables and 27 constraints. Eight of the constraints are equality constraints. ORTOOL adresses the equalities rather mechanically by the big-M method. However, seven of the eight equality constraints have a zero right hand side. Thus, the initial solution of the related big-M problem is highly degenerated. Trying to maximize the big-M objective, ORTOOL will eliminate one big-M variable after another – in the beginning without improving the objective value of neither the original nor the big-M problem. Note that the revised method of the steepest ascent will not switch to Bland's rule when dealing with the degenerated case of a zero big-M variable. This is because there is no risk of cycling as the big-M variable leaving the basis will be deleted after the tableau update.