Branch-and-Bound integer/float

回答済み

Theresa Reinhardt

2021年09月06日 15:49

• 
• 
• 

Hi.

Gurobi is using the branch-and-bound/cut-method for optimization. According to literature the aim of this method is to find an optimal integer solution by going through the search tree. But the solution of my optimisation is of the data type float. So does Gurobi return the optimal solution solved with e.g. simplex unless the user tells the optimizer that some specified variables should be integers or am I wrong about that?

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 02:48 編集済み

  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?.
• 

  Jaromił Najman

  • Gurobi Staff

  2021年09月08日 09:47

  Hi Tessa,

  Working with floating numbers instead of true integers is common practice in numerical algorithms. This is due to the fact that machine precision is not infinite. Thus, optimization solvers work with integrality tolerances (IntFeasTol in Gurobi). As a result, it is possible that the optimal solution value of an integer or a binary variable is reported as, e.g., 0.999999 instead of 1. Recently, Gurobi introduced the IntegralityFocus parameter to tackle this issue and spend more effort to determine true integer values for binary and integer variables. However, this comes with a price hurting the overall performance.

  So does Gurobi return the optimal solution solved with e.g. simplex unless the user tells the optimizer that some specified variables should be integers or am I wrong about that?

  If your problem does not contain any discrete variables, then Gurobi will provide the solution found by one of the Simplex algorithms or the Barrier algorithm (depending on which one is fastest for a given instance). If your problem has discrete variables, then feasible points are determined via various heuristics which try to make the solution values of discrete variables as integer as possible and accept non-integer values up to the tolerance given by the IntFeasTol parameter.

  If you are interested in the topic of numerical accuracy, I recommend having a glance at the book by Nicholas Higham on Accuracy and Stability of Numerical algorithms for more insight.

  Best regards,
  Jaromił

  0

投稿コメントは受け付けていません。