nuget
A two-phased simplex solver which is implemented in the sparse matrix format with the bounded variable support.
LPPSolverTwoPhased
00 Remarks
why this solver is re-written
the previous implementation of this solver class have some critical bugs and performance problems:
- the basic variables was re-calculated from the tableau via a "unit vector" scanning helper, which costs O(m^2 * n) and will fail on the numerical noise, result in a full zero solution.
- the phase 1 objective includes the slack variables, and the reduced cost row is never priced out against the initial basis.
- the tableau was stored in a dense format, which runs out of the memory on the genome scale metabolic network problem.
this implementation maintains the basic variable list explicitly, handles the variable bounds in the ratio test (bounded simplex), and runs the pivot elimination in parallel.
01 Syntax
Microsoft.VisualBasic.Math.LinearAlgebra.LinearProgramming.LPPSolverTwoPhased
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| Solve | 1 | solve the linear programming problem |
| normType | 1 | normalize the constraint type symbol |
| Build | 1 | build the working tableau of the simplex method |
| BuildVariableMapping | 1 | the variables with a negative lower bound will be splitted into two non-negative variables, and the variables with a positive lower bound will be shifted, so that all of the work… |
| BuildTableau | 1 | build the sparse simplex tableau in the standard form |
| PurgeArtificialColumns | 1 | the artificial variables are excluded from the entering variable candidate list forever, so that the tableau columns of the artificial variables are never be used by the simplex… |
| PriceOut | 1 | d(j) = c(j) - cB * B^-1 * A(j), the reduced cost row is priced out against the current basis. |
| ResetObjective | 1 | re-calculate the objective function value from the scratch |
| ChooseEntering | 1 | choose the entering variable via the Dantzig rule, the Bland rule is applied when the degenerate iteration is detected. |
| ExtractColumn | 1 | extract the pivot column from the sparse tableau |
| Pivot | 1 | do the pivot operation at tableau(r, q), note that the value of the basic variables is updated by the caller. |
| RunSimplex | 1 | run the bounded simplex iteration until the optimal solution is reached. |
| NeedsPhase1 | 1 | checks whether the initial basis is already a feasible solution of the original problem: all of the artificial variables are zero. |
| Phase1 | 1 | phase 1: minimize the sum of the artificial variables for seeking an initial basic feasible solution. |
| Phase2 | 1 | phase 2: optimize the original objective function |
| DriveArtificialsOut | 1 | drive the artificial variables out of the basis, the constraint row will be marked as a redundant row when the artificial variable can not be pivoted out. |
| ExtractSolution | 1 | collect the solution of the original variables from the working tableau. |
03 Properties
| Name | Overloads | Summary |
|---|---|---|
| iterationLimit | 1 | the iteration upper bound is scaled by the problem size |
04 Fields
| Name | Overloads | Summary |
|---|---|---|
| b | 1 | the current value of each basic variable, index by row |
| hi | 1 | the upper bound of each variable, INF means no upper bound |
| c | 1 | the objective coefficient of the current phase |
| d | 1 | the reduced cost of each variable, always in a dense format |
| basis | 1 | basis(row) = the column index of the basic variable |
| status | 1 | 0 = at lower bound(zero), 1 = basic, 2 = at upper bound |
| rowActive | 1 | false when the constraint row is a redundant row |
| alpha | 1 | the cached pivot column |
| ratioBuf | 1 | the ratio test buffer, a negative value means not a candidate |
| kindBuf | 1 | 1 = blocked by the lower bound, 2 = blocked by the upper bound |
| blocked | 1 | the entering variable candidate which is rejected by the pivot element threshold check |
| artBase | 1 | the first column index of the artificial variables, all of the columns after this index can be removed from the tableau. |
05 Members
Solve(
Boolean)solve the linear programming problem
normType(
String)normalize the constraint type symbol
Build(
StringBuilder, Boolean)build the working tableau of the simplex method
BuildVariableMapping
the variables with a negative lower bound will be splitted into two non-negative variables, and the variables with a positive lower bound will be shifted, so that all of the working variables have a zero lower bound.
BuildTableau(
StringBuilder)build the sparse simplex tableau in the standard form
PurgeArtificialColumns
the artificial variables are excluded from the entering variable candidate list forever, so that the tableau columns of the artificial variables are never be used by the simplex iteration: keeping these columns in the tableau will produce a huge amount of the fill-in (the column of an artificial variable is a column of the B^-1, which is a dense vector in general).
PriceOut
d(j) = c(j) - cB B^-1 A(j), the reduced cost row is priced out against the current basis.
ResetObjective
re-calculate the objective function value from the scratch
ChooseEntering(
Boolean)choose the entering variable via the Dantzig rule, the Bland rule is applied when the degenerate iteration is detected.
ExtractColumn(
Int32)extract the pivot column from the sparse tableau
Pivot(
Int32, Int32)do the pivot operation at tableau(r, q), note that the value of the basic variables is updated by the caller.
RunSimplex(
Int32, StringBuilder, Boolean, String)run the bounded simplex iteration until the optimal solution is reached.
Returns
the error message, nothing when the iteration is converged
NeedsPhase1
checks whether the initial basis is already a feasible solution of the original problem: all of the artificial variables are zero.
Phase1(
StringBuilder, Boolean)phase 1: minimize the sum of the artificial variables for seeking an initial basic feasible solution.
Phase2(
StringBuilder, Boolean)phase 2: optimize the original objective function
DriveArtificialsOut
drive the artificial variables out of the basis, the constraint row will be marked as a redundant row when the artificial variable can not be pivoted out.
ExtractSolution
collect the solution of the original variables from the working tableau.
iterationLimit
the iteration upper bound is scaled by the problem size
b
the current value of each basic variable, index by row
hi
the upper bound of each variable, INF means no upper bound
c
the objective coefficient of the current phase
d
the reduced cost of each variable, always in a dense format
basis
basis(row) = the column index of the basic variable
status
0 = at lower bound(zero), 1 = basic, 2 = at upper bound
rowActive
false when the constraint row is a redundant row
alpha
the cached pivot column
ratioBuf
the ratio test buffer, a negative value means not a candidate
kindBuf
1 = blocked by the lower bound, 2 = blocked by the upper bound
blocked
the entering variable candidate which is rejected by the pivot element threshold check
artBase
the first column index of the artificial variables, all of the columns after this index can be removed from the tableau.