memory footprint due to tableau

[TianBo-Timothy]

The tableau used in the implementation is unnecessary.

Even though most books regarding simplex algorithm will illustrate the algorithm by constructing a tableau, it does not mean we need to construct one. The problem of using the tableau is the memory consumption:

this->tableau.resize(constraints.rows() + 1, this->numberOfVariables + constraints.rows() + 1);

The above line shows that the size of the tableau will be (number of constraints) x (number of variables + number of constraints), which can be huge thus hinder the application for large problems (for example, with constraints over 100 thousand).

The tableau can be removed if we consider the non-basis variables as a linear combination of the basis variables. A matrix of size (number of constraints) x (number of variables) can be used to track the relationship. The size of this matrix is much smaller than the tableau.

[TianBo-Timothy]

One example of large linear programming problem can be Least Absolute Regression. The number of data sample can easily reach a large number and therefore lots of constraints are created when converting to a linear programming problem.