The Effect of Preprocessing on Feasibility

CPLEX preprocessing may declare a model infeasible before the selected optimization algorithm begins. This saves considerable execution time in most cases. It is important, when this is the outcome, to understand that there are two classes of reductions performed by the preprocessor.

Reductions that are independent of the objective function are called primal reductions; those that are independent of the right-hand side are called dual reductions. Preprocessing operates on the assumption that the model being solved is expected by the user to be feasible and that a finite optimal solution exists. If this assumption is false, then the model is either infeasible or no bounded optimal solutions exist, i.e. unbounded. Since primal reductions are independent of the objective function, they cannot detect unboundedness, they can only detect infeasibility. Similarly, dual reductions can only detect unboundedness.

Thus, to aid analysis of an infeasible or unbounded declaration by the preprocessor, a parameter is provided that the user can set, so that the optimization can be rerun to assure that the results reported by the preprocessor can be interpreted. If a model is declared by the preprocessor to be infeasible or unbounded and the user believes that it might be infeasible, the parameter IloCplex::Reduce or CPX_PARAM_REDUCE (set preprocessing reduce in the Interactive Optimizer) can be set to 1 by the user, and the preprocessor will only perform primal reductions. If the preprocessor still finds inconsistency in the model, it will be declared by the preprocessor to be infeasible, instead of infeasible or unbounded. Similarly, setting the parameter to 2 means that if the preprocessor detects unboundedness in the model, it will be declared unambiguously to be unbounded.

These parameters are intended for diagnostic use, as turning off reductions will usually have a negative impact on performance of the optimization algorithms in the normal (feasible and bounded) case.


Previous Page: Diagnosing LP Infeasibility  Return to Top Next Page: Coping with an Ill-Conditioned Problem or Handling Unscaled Infeasibilities