ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Solving Mixed Integer Programming Problems (MIP) > Troubleshooting MIP Performance Problems > Slightly Infeasible Integer Variables |
Slightly Infeasible Integer Variables |
INDEX PREVIOUS NEXT |
On some models, the integer solution returned by ILOG CPLEX at default settings may contain solution values for the discrete variables that violate integrality by a small amount. The integrality tolerance parameter (EpInt
, CPX_PARAM_EPINT
) has a default value of 1e-5, which means that any discrete variable that violates integrality by no more than this amount will not be branched upon for resolution. For most model formulations, this situation is satisfactory and avoids branching that may be essentially meaningless, only consuming additional computing time.
However, some formulations combine discrete and continuous variables, for example, involving constraint coefficients over a million in magnitude, where even a small integrality violation can be magnified elsewhere in the model. In such situations, you may attempt to address this variation by tightening the simplex feasibility tolerance (EpRHS
, CPX_PARAM_EPRHS
) from its default value to its minimum; also tighten EpInt
to a similar value, and re-run the MIP optimization from the beginning.
If this adjustment is insufficient to give satisfactory results, you can also try setting EpInt
all the way to zero, preferably in conjunction with a tightened EpRHS
setting. This very tight integrality tolerance directs ILOG CPLEX to attempt to branch on any integer infeasibility, no matter how small. Numeric roundoff due to floating-point arithmetic on any computer may make it impossible to achieve this tolerance, but in practice, the setting achieves its aim in many models and reduces the integrality violations in many others. In cases where the integrality violation even after branching remains above EpInt
or is above 1e-10 when EpInt
has been set to a value smaller than that, a solution status returned will be CPX_STAT_OPTIMAL_INFEAS
instead of the usual CPX_STAT_OPTIMAL
. In most cases a solution with status CPX_STAT_OPTIMAL_INFEAS
will be satisfactory, and reflects only roundoff error after presolve uncrush, but extra care in using the solution may be advisable in numerically sensitive formulations.
If these suggestions are not appropriate for your problem, another alternative to consider is reformulation of your model with indicator constraints. Using Indicator Constraints offers more information about that alternative.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |