Updating of Best Bound based on integrality of objective function value (due to integer coefficients and integer decision variables)

Answered

Hendrik Weber

• August 18, 2020 13:54
• Edited

Hello 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 branch-and-bound.

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

 

 

1

• Official comment

  

  Simranjit Kaur

  Gurobi Staff

  • December 06, 2024 00:42

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Eli Towle

  Gurobi Staff

  • August 18, 2020 21:37
  • Edited

  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 integer-valued incumbent objective value.

  0
• 

  Hendrik Weber

  • August 19, 2020 08:10

  

  

  

  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 (integer-valued) 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 variable-types (integer or continuous) could be chosen without changing the model.
  For instance: Introducing a "helper"-variable that simply represents the absolute value of another integer-valued decision variable.

  This helper-variable will always be integer-valued, 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
• 

  Eli Towle

  Gurobi Staff

  • August 21, 2020 02:20

  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

Post is closed for comments.