Originally posted by: SystemAdmin

Hi,
When all coefficients in the objective function are integer and all variables are integer, it is possible to round the bound arising from the LP relaxation to an integer. Does Cplex do that by default ? Or is there a parameter to set ?
Thanks
Christophe
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't think there's a way to get CPLEX to round the LP bound, or to recognize that the objective value needs to be integral. The coefficients may be integers to you, but their double-precision reals to CPLEX. I have no idea whether anyone has ever entered a feature request to check for all-integer objective functions and round LPs downward. It seems a reasonable thing to want. One caveat is that you would be forcing CPLEX to decide whether a coefficient within epsilon of an integer was deliberately non-integer or the result of rounding/truncation error.

You can get some of the benefit of an all-integer objective function with a couple of parameters. If you change ObjDif from its default of 0.0 to 1.0 - epsilon, then CPLEX will ignore nodes whose LP bounds are not at least 1.0 - epsilon better than the (integer) objective value of the current incumbent. I suspect that buys you most of the benefit of knowing that the objective value is integer. The other parameter to look at would be EpAGap (default 1e-6). If you change that to 1 - epsilon, then CPLEX will stop the search as soon as the LP bound of the best surviving node rounds down to the current incumbent value.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

CPLEX does not round the LP bound explicitly (since the values of CPXgetx() and CPXgetobjval() would not match). What CPLEX does instead is: if the objective function is integral (all variables binary or integral and all coefficients integral) and we have an incumbent with objective function value z then all nodes with objective function value larger than z-1 can be pruned. This is essentially the same as rounding the LP bound.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you very much Daniel, this is exactly the kind of answer I was looking for.
Just a last question: is this documented somewhere ? And if yes, where ?
Christophe
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> chMeyer wrote:
> Thank you very much Daniel, this is exactly the kind of answer I was looking for.
> Just a last question: is this documented somewhere ? And if yes, where ?
> Christophe

I don't believe this is documented anywhere. This is an internal feature, and it could change in upcoming releases. For example, when you have an all integer objective with a greatest common divisor > 1, the nature of the pruning changes. We don't know what additional pruning criteria we will derive in future releases, and documenting each such change would be of limited benefit to our readers. The key point here from a user perspective is that CPLEX makes a serious effort to use the nature of the objective function coefficients to do additional pruning. So, if you are trying to improve performance on your models, you probably shouldn't invest time trying to derive general algebraic pruning schemes based on the objective function.
You are more likely to benefit from a scheme based on specific features of your model that cannot be derived on an arbitrary IP.
#CPLEXOptimizers
#DecisionOptimization