Branch and Bound Algorithm: How to choose variables?

Question

In Branch and Bound Algorithm, if the linear relaxation of the problem provides more than one fractional values (for more than one decision variables), then which decision variable should be considered for the next step? If arbitrarily any one of the fractional values is chosen, does it guarantee the optimal solution finally?

Answer 1

There are many possible variable selection strategies. One is to choose the variable with maximum integer infeasibility. Another one is to do the opposite: choose the variable with minimum integer infeasibility. Most solvers provide a choice of variable selection strategies (including some advanced ones such as pseudo cost and strong branching). Consult the documentation of your solver for more information.

Yes. A poor choice will still get you the proven optimal solution eventually. For an end-user the essential considerations are solution time or memory consumption (e.g. tree becomes too big).