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?
Dear parag
If you have more than one fractional value in L. L. P. Then we take greatest integer of maximum fractional value. For example first fractional value is7.5& second fractional value is 5.8. Then we consider greatest integer of maximum fractional value which is 7.Then repeat algorithm to find optimal solution.
Sharandeep singh
Assistant professor of mathematics
Typically, there are many integer variables with fractional values, so we must have a method for deciding which one to choose (these methods are called branching methods). The simplest branching methods are those that select the variable based only on the existing fractional variables and do not require additional information. Example of these methods are: first branch the variable with the largest fractional part (tenth closest to 5); the variable closest to an integer; the first non-integer variable (in order of declaration of variables); the last variable not integer (in order of declaration of variables).
Many solvers use more sophisticated approaches. Such approaches fall into two general categories: forward-looking methods and backward-looking methods. Both types of methods try to choose the best partitioning by predicting, for a given candidate partitioning, how much the lower bound will be improved. Forward-looking methods generate this prediction based solely on locally generated information obtained by “pre solving” candidate subproblems. Backward-looking methods take into account the results of previous partitionings to predict the effect of future ones.
The most common failure in ILP (Integer linear programming) is the result of an exessive search that exceeds the virtual computing capacity. So the arbitrary branching can lead you to this failure. The remaining efficiency of branching strategies will depend on the model being analyzed.
For more detail I recommend
Linderoth, J., & Ralphs, T. (2005). Noncommercial Software for Mixed-Integer Linear Programming. Integer Programming: Theory and Practice, 253-303.
Thank you very much for your kind and valuable reply. Thanks to all of you.
So, to conclude, the largest fractional value should be chosen for the next step among all the fractional values of the decision variables (if found or exists). But in case of minimization problem, is it also the same?
It is one possibility to always choose the larges fractional value - but by no means the only one. The choice of the branching variable especially in the beginning is very important for the size of the resulting tree.
Unfortunately there is no way to know the optimal choice a priori,
The answer of Daniel Molina Pérez pointed out two means incorporated in many solvers.
The backwards looking one is called pseudo costs branching in CPLEX. It records the changes in the LP bound by branching on the variables and chooses one which gave the greatest change. Of course this information is not available in the beginning.
The forward looking one is called strong branching and does a limited number of simplex steps on some chosen candidate branching variables to see which one gives the greatest improvement of the bound.
There is a third way offered by most solvers: that the user (who knows his model much better than the solver) identifies 'important' variables by assigning a higher branching priority.
The choice of the next node in the front of the tree is another important point. Always choosing the one with worst bound is a possibility - but not the most clever one. Besides improving the total dual bound there is another question: Which one is the most probable to yield a good integer feasible solution? The better the primal bound, the more the growth of the B&B tree could be limited (cutoff due to inferiority).
I really encourage you to do a literature search. Have a look to Wolsey's book, too.
Besides the choice of the branching variable and the next node the implementation of clever heuristics is very important, too, since early knowledge of good primal bounds would allow for earlier inferiority cutoffs and reduces the size of the B&B tree considerably.
The excellent commercial solvers like Gurobi and CPLEX contain a lot of techniques to speed up the solution process and their defaults are carefully tuned to a large set of test problems . But though these defaults perform best 'in the mean' still the right choice of parameters for any particular MIP is a kind of art.
kindly, I need to know what is the name of this technique" select the largest fraction part to branch on" is that the least /most variable selection or is there a difference between them? Also, this technique is used for minimization problems without change, or should we select the smallest fraction part in this case?
thank you @@
Here are the names of the strategies for variable selection in CPLEX:
CPLEX> set mip stra var Present value for variable selection strategy: 0 (default is 0) -1 = minimum integer infeasibility 0 = automatic 1 = maximum integer infeasibility 2 = pseudo costs 3 = strong branching 4 = pseudo reduced costs
and these are the node selection strategies available:
CPLEX> set mip str nod Present value for node selection strategy: 1 (default is 1) 0 = depth-first search 1 = best-bound search 2 = best-estimate search 3 = alternate best-estimate search
Of course these are the same - whether it's minimization or maximization. Just draw a two-dimensional image of a polyhedron with the integer points in it and consider how branching on each of both variables would affect the new relaxation solutions.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Programming Languages
- Python