search

bolner / SimplexSolver

An easy-to-use Simplex solver class for linear programming.
Other
18 stars 8 forks source link

memory footprint due to tableau #1

Open TianBo-Timothy opened 6 years ago

TianBo-Timothy commented 6 years ago

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 commented 6 years ago

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.