Preprocessing and Feasibility

ILOG CPLEX preprocessing may declare a model infeasible before the selected optimization algorithm begins. This early declaration saves considerable execution time in most cases. When this declaration is the outcome of preprocessing, it is important 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 righthand side (RHS) of the constraints 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; that is, it is unbounded. Since primal reductions are independent of the objective function, they cannot detect unboundedness, they can detect only infeasibility. Similarly, dual reductions can detect only 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 make sure 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 Reduce 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.

To control the types of reductions performed by the presolver, set the Reduce parameter to one of the following values:

These settings of the Reduce parameter 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.