Question & Answer
Question
What does the simplex feasibility tolerance signify?
Answer
The simplex feasibility tolerance (controlled by the CPX_PARAM_EPRHS/ IloCplex::EpRHS parameter), in some sense, controls the accuracy of the solution at each simplex iteration.
The constraints in a model may be in the Ax<=b / Ax>=b / Ax=b form, but after the regular standardization procedure (and the addition of slack variables), all of them will be transformed into equality constraints. Lets consider one such system of equations in the Ax = b form. Now, for a particular simplex iteration, lets assume x_B and x_N to be basic and non-basic variables (A_B and A_N are the basic and non-basic matrix coefficients corresponding to the basic and non-basic variables) which together form xj.
Thus, to calculate the basic variables, the non-basic variables are first set at their bounds and then the following formulae are used (_inv denote the inverse matrices):
Ax = b
or A_B * x_B + A_B * x_N = b
or A_B_inv * A_B * x_B = A_B_inv * (b - A_N * x_N)
or x_B = A_B_inv * (b - A_B * x_B)
This is where the feasibility tolerance is used. It defines the amount by which x_B can violate their bounds without deeming the model as infeasible. The non-basic variables do not have any bound violations since they are already set at the bounds.
For information related to the Simplex optimality tolerance click here.
Details about how tolerance settings can affect the feasibility of a computed solution can be found here.
Was this topic helpful?
Document Information
Modified date:
16 June 2018
UID
swg21567635