bolner/simplexsolver

An easy-to-use Simplex solver class for linear programming.

simplexsolver's Issues

memory footprint due to tableau

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.