LA04: Sparse linear programming: steepest-edge simplex method

This package uses the simplex method to solve the linear programming problem \[\text{minimize } \mathbf {c} ^T \mathbf{ x} = \sum_{ j=1} ^ n c _j x _j\] subject to the constraints \[\begin{aligned} &\mathbf {Ax} = \mathbf {b}, \; \text{that is,} \; \sum_{ j=1} ^ n a _{ij} x _j = b _i, \; i = 1, 2, ... m \\ &l _j \le x _j \le u _j, \; 1 \le j \le k, \\ &\qquad x _j \ge 0, \quad l \le j \le n.\end{aligned}\]

The variables \(x _j\), \(k+1 \le j \le l-1\), if any, are free (have no bounds). Full advantage is taken of any zero coefficients \(a _ {ij}\). The inequalities \(0 \le k < l \le n+1\) must hold. Special values \(l _i = - \sigma\) and \(u _i = \sigma\) may be used to remove one or both bounds.

To accommodate roundoff, all variables are permitted to lie slightly outside their bounds.

Precision: At least 8-byte arithmetic is recommended.