IBM Support

Simplex Feasibility Tolerance

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.

[{"Product":{"code":"SSSA5P","label":"IBM ILOG CPLEX Optimization Studio"},"Business Unit":{"code":"BU059","label":"IBM Software w\/o TPS"},"Component":"Linear Programming","Platform":[{"code":"PF002","label":"AIX"},{"code":"PF010","label":"HP-UX"},{"code":"PF016","label":"Linux"},{"code":"PF022","label":"OS X"},{"code":"PF027","label":"Solaris"},{"code":"PF033","label":"Windows"}],"Version":"9.2;9.1.3;9.1.2;9.1;9.0;8.1;8.0;7.5;7.1;7.0;6.6;12.4;12.3;12.2;12.1;12.0;11.2.1;11.2;11.1.1;11.1;11.0.1;11.0;10.3;10.2.1;10.2;10.1.1;10.1;10.0","Edition":"All Editions","Line of Business":{"code":"LOB10","label":"Data and AI"}},{"Product":{"code":"SSSA5P","label":"IBM ILOG CPLEX Optimization Studio"},"Business Unit":{"code":"BU059","label":"IBM Software w\/o TPS"},"Component":"Linear Programming","Platform":[{"code":"PF002","label":"AIX"},{"code":"PF010","label":"HP-UX"},{"code":"PF016","label":"Linux"},{"code":"PF017","label":"Mac OS"},{"code":"PF027","label":"Solaris"},{"code":"PF033","label":"Windows"}],"Version":"12.4;12.3;12.2.0.1;12.2","Edition":"All Editions","Line of Business":{"code":"LOB10","label":"Data and AI"}},{"Product":{"code":"SSSA5P","label":"IBM ILOG CPLEX Optimization Studio"},"Business Unit":{"code":"BU059","label":"IBM Software w\/o TPS"},"Component":"Features:Mathematical Programming (CPLEX)","Platform":[{"code":"PF002","label":"AIX"},{"code":"PF033","label":"Windows"}],"Version":"12.2;12.3;12.4;3.0.2;3.1;3.5;3.5.1;3.6;3.6.1;3.7;3.7.1;4.0;4.0.1;4.1;4.2;5.0;5.1;5.2;5.5;5.5.1;6.0;6.0.1;6.1;6.1.1;6.2;6.3","Edition":"All Editions","Line of Business":{"code":"LOB10","label":"Data and AI"}}]

Document Information

Modified date:
16 June 2018

UID

swg21567635