Integer linear optimization: Branch & Bound 2
Branch and Bound
Idea: Splitting the set of all possible solutions into disjoint (i.e. not overlapping) subsets and evaluating these subsets;
to reach the optimal solution fast and efficiently.
Approach:
1. Set up simplex tableau and calculate the continuous optimum
2. Branching branch according to the structure variable xi in the basis with the largest part of the fraction -> substitute column:
• next higher integer number becomes lower bound: xi -> xi´= xi – li ; bineu= bi - li
• next lower integer number becomes upper bound: xi -> xi ̅ = ui – xi ; bineu = ui - bi
+ all aij of that row change signs
3. Bounding calculate new sub-optimum. Continue with the largest objective function value, where the node hasn´t been processed yet.
4. End if
• solution is integer number
• when there is no node which hasn´t been processed has no higher objective function value
• all nodes are processed -> choose node with the highest objective function value
Notice: The right side is always negative and determines the new pivot-row.
If all row-coefficients ais > 0, then the approach is inadmissible. If there is a second row, then this one is also to analyze.
Otherwise:
• If there is only one row-coefficient which is negative, then this coefficient determines the pivot-element (PVE)
• If several row-coefficients are negative, you have to determine a quotient out of the objective function value and the row-coefficient (Dual Simplex Method) -> the quotient with the absolute minimal value constitutes the new PVE. -> Perform simplex-transformation while the extra-row substitutes the old restriction.
Example:
Maximize the profit
G = 4x1+3x2
With the restrictions:
2x1+x2 <= 8 x1+2x2 <= 8
Non-negativity restriction
x1,x2 >= 0, integer
Steps:
Set up simplex tableau and calculate the continuous optimum
Initial Tableau:
Fig. 1 Initial Tableau
After the first iteration you get this tableau:
Fig. 2: First iteration
After the second and last iteration you get the following continuous optimum:
Fig. 3: Continous optimum
The solution is not integer, so we have to determine a source row. We have to choose the row with the largest fraction on the right side. In this case we have identical values on the right side, so we can choose one of these two rows.
We opt for x2.
Source Row: x2+y1*-1/3+y2*2/3=2 2/3
a) Additionaly to the previous restictions: next higher integer number becomes lower bound, so the lower bound (li) is x2>=3 -> x2 has to be replaced by x2´
x2´= x2 – l2 = 2 2/3 – 3 = - 1/3
b) Additionaly to the previous restrictions: next lower integer number becomes upper bound, so the upper bound (ui) is x2<=2.
-> x2 has to be replaced by x2 ̅ and all signs of ais must be reversed.
x2 ̅ = u2 – x2= 2 - 2 2/3 = - 2/3
Fig. 4: Tableau 1a
a) New row for x2: x2´+y1*-1/3+y2*2/3= -1/3
Resulting tableau:
Fig. 5: Tableau 1b
b) New row for x2: +y1*1/3+y2*-2/3= -2/3
Resulting tableau:
Fig. 6 Tableau 1c
Both tableaus (Fig. 5 and 6) have negative elements on the right side. So we have to determine the optimal solutions with the simplex method again.
The Column which we have chosen before becomes our new pivot column and choose the negative ais as the pivotelement.
Therefore our optimal solutions are:
Fig. 7: Optimal solution to 1b
Fig. 8 Optimal solution to 1c
Both tableaus have integer values on the right side.
The objective function value of b) is larger than a)
-> Tableau b) represents the optimal solution:
z = 18
x1 = 3
x2 ̅ = 0
x2 = ui - x2 ̅ = 2 – 0 = 2
Sources
Operations Research Script
Operations Research Wiki
