Branch and Bound examples

Branch and Bound . General purpose method to solve discrete optimization problems
> Takes exponential time in the worst-case
> Useful to solve small instances of hard problems
. Can be applied to all scheduling problems
. Need to specify: 1. A lower bounding scheme
2. Branching rule
3. Search rule (subproblem selection rule)
. Overview: For a minimization problem, at a given branch and bound tree (b&b) node i: 1. Obtain a lower bound, lbi
2. (Optional) Obtain a candidate solution and an upper bound ubi
3. If (ubi < GLOBAL UB) then set ubi as the GLOBAL UB
4. If (lbi >= GLOBAL UB) then prune the node and go to 6.
5. Branch into subproblems (create child nodes)
6. Pick the next active subproblem.
If none exist, stop. Else, go to 1. Example 1 Problem: Single machine, n jobs arriving at different times, preemptions
not allowed, minimize maximum lateness (Lmax) . A b&b node corresponds to a partial schedule . At level k of the b&b tree, the first k jobs in the schedule have been
fixed . Branching Create a child node of a node at level k-1 by fixing each remaining job
at kth position EXCEPT:
If a job c satisfies [pic],
do not create a child for that job . Lower bounding: Schedule remaining jobs according to the preemptive EDD rule: Every time the machine is freed or a new job is released,
pick the uncompleted job with minimum due date Numeric Example: |Jobs |1 |2 |3 |4 |
|pj |4 |2 |6 |5 |
|dj |8 |12 |11 |10 |
|rj |0 |1 |3 |5 | Lower bound at node (1,-) is obtained by applying preemptive EDD to jobs 2,
3 and 4 with starting time 4 At t=4, available jobs: 2, 3, pick 3
At t=5, available jobs: 2, 3,4 pick 4
At t=10, available jobs: 2, 3, pick 3
At t=15, available jobs: 2, pick 2 L1 = -4, L2 = 5, L3 = 4, L4 = 0, Lmax = 5 Exercise: Calculate the lower bound at node (2,-) Preemptive EDD at node (1,3,-) gives a non-preemptive schedule 1, 3, 4, 2
with Lmax = 5 and it is an optimal solution to the problem
-----------------------
Level 0 0 Level 1 lb= 5 4, 3, 2, 1, prune prune lb= 7 Level 2 1,3, 1,2, lb= 5 lb= 6 Level 3 ub= 5
candidate 1,3,4,2 3 1 3 4 2 4 5 100 15 17