AIMMS Knowledge Base Article – KB000018
Math Program infeasible with presolve and feasible without presolve
The presolve phase of CPLEX seems to be more sensitive to the feasibility tolerance than the simplex phase.
When you solve your math program with presolve it is infeasible, while solving it without presolve returns a feasible solution.
A constraint ‘ax <= b’ is satisfied if and only if
| ax – b | <= feasibility tolerance.
Assume that the feasibility tolerance = 1e-7 and that we have the following model:
|minimize||x1 +x2 + x3|
|s.t.||x1 = 0.7e-7 (1)|
|x1 + x2 = 0 (2)|
|x1 + x3 = 0 (3)|
|x2 + x3 = 0 (4)|
The simplex method will at some point find a solution x1 = 0.7e-7, x2 = 0, x3 = 0 and this solution satisfies all constraints with the feasibility tolerance of 1e-7. And therefore the simplex method (without presolve) returns a feasible solution.
The presolve tries (amongst others) to eliminate variables. After constraint (1) it knows that x1 = 0.7e-7. After constraint (2) it concludes that x2 = -0.7e-7 and after constraint (3) it concludes that x3 = -0.7e-7. Then it tries to fill this in, in constraint (4) and gets -1.4e-7 = 0, which violates the infeasibility tolerance of 1e-7. The presolve will return that this model is infeasible.
When the presolve returns an infeasibility for your model, the model is probably not formulated correctly. You should take a look at your model and try to reformulate it.
For more information, please contact us at firstname.lastname@example.org.