Integer linear optimization: Branch & Bound 1
Conceptual explanation:
Procedure of Operations Research for exact and optimal solution of a combined optimization problem (finite number of independent variables with discrete values).
Idea:
Breakdown of quantity of all possible solutions in disjoined (not overlapped) subset, followed by the evaluation of the subset.
Approach:
1) Establish the Simplex Tableau and the continuous optimum.
2) Branching according to the structure variable xi in the basis with the maximal brake-share (replace row):
Nearest higher integer number will be the lower bound: xi → xi ‘ (= xi –li) ; bi new = bi -li
Nearest lower integer number will be the upper bound: xi →x ̅I (= ui-xi) ; bi new = ui-bi & all aij of the row change the sign.
3) Bounding: calculate the new suboptimum. In the next step you take the next not processed node with the highest objective function value. You have finished if the solution is integer and there is no unprocessed node with a higher objective function value or rather all nodes are processed.
Important:
1)The right side is always negative and determines the pivot row. If all row coefficients ais >0, than it is the prohibited solution. (If there is a second row than you should investigate it.)
2) The value of the continuous optimum rounded down to the nearest integer number is the maximal reached border for the objective function value of one of the sub optima. If you reach at a suboptimum exactly the same value, than you have found the optimal solution for the tested branch.
