Updating of Best Bound based on integrality of objective function value (due to integer coefficients and integer decision variables)
AnsweredHello Gurobi community,
We are currently solving a MILP (minimisation problem) where all objective function coefficients are integral.
Furthermore, we require decision variables to be integer as well. This will then result in the objective function value being integral as well as far as I am concerned.
Is there any way to incorporate this idea (for instance by explictly telling the solver that the objective function value will be integer) to update the "best bound"? This would then result in a faster termination of the branchandbound.
For example:
Min Problem with incumbent of z=23.0.
Best Bound: 22.34215
I think the best bound could be rounded up to 23.0, therefore proving optimality of the found incumbent.
As of now, the gap only slowly closes, even though we have already found the optimal solution and could terminate the algorithm.
Or is my thinking wrong here?
Appreciate the help!
Edit: TL;DR: Is there a way to round the best bound (up or down depending on min or max problem) if we know that the objective function value has to be integer?
Hendrik

You could set the absolute MIP gap (MIPGapAbs parameter) to a number slightly less than 1. With this approach, Gurobi will terminate when the ceiling (for minimization) of the best bound is equal to the integervalued incumbent objective value.
0 
Clean and easy solution, thanks for the help, Eli.
I also did another change: I explicitly declared the decision variables that appear in the objective function as Integer.
[I previously did not do that because the way the model is written, these decision variables will automatically be integer because their values are based on other (integervalued) decision variables in corresponding constraints.]
This also resolved the issue, as the solver seems to be aware of this whole aspect of ceiling of best bound when the relevant decision variables are explicitly declared as integer.
Just a general question, now that I think of it:Is it generally advisable to not use integer variables whenever possible? I am specifically talking about cases, where both variabletypes (integer or continuous) could be chosen without changing the model.
For instance: Introducing a "helper"variable that simply represents the absolute value of another integervalued decision variable.This helpervariable will always be integervalued, however is there a "best practice" regarding the declaration (int or continuous) of the decision variable? Or does this simply not matter?
Thanks a lot for the help!
Greetings from Germany
Hendrik
0 
I'm not sure if it's always better to define such variables as continuous or integer. Ideally, it wouldn't matter much either way. Using a continuous variable seems reasonable, since the solver has one less constraint to deal with. However, if the variable is defined to be integer, Gurobi may exploit this integrality in presolve, during certain heuristic routines, in branching, or (as you observed) to draw conclusions about the integrality of the objective function.
0
Please sign in to leave a comment.
Comments
3 comments