Basic Branch Bound 0bj:15W+10P+7C 4w+3P+2C≤9 Current Best:0 15W+10P+7C230 W=0 P=1 The subtree of C=4(in green)is pruned,since 4*0+3*1+2*4 >9. Now max(C)=3 Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:0 15W+10P+7C≥30 W=0 P=1 15*0+10*1+7*max(C)=0+10+21=31 16
16 MSC Seminar (January 30, 2012) Basic Branch & Bound W=0 P=1 The subtree of C=4 (in green) is pruned, since 4*0+3*1+2*4 > 9. Now max(C) = 3 Obj: 15W + 10P + 7C Current Best: 0 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*1 + 7*max(C) = 0 + 10 + 21 = 31 W=0 P=1 Obj: 15W + 10P + 7C Current Best: 0 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30
Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:0 15W+10P+7C230 W=0 P=1 15*0+10*1+7*0=0+10+0=10<30 Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:0 15W+10P+7C≥30 W=0 P#1 15*0+10*1+7*1=0+10+7=17<30 17
17 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*1 + 7*0 = 0 + 10 + 0 = 10 < 30 W=0 P=1 C=0 Obj: 15W + 10P + 7C Current Best: 0 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*1 + 7*1 = 0 + 10 + 7 = 17 < 30 W=0 P=1 C=1 Obj: 15W + 10P + 7C Current Best: 0 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30
Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:0 15W+10P+7C230 W=0 P=1 15*0+10*1+7*2=0+10+14=24<30 Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:0 15W+10P+7C≥30 W=0 P1 15*0+10*1+7*3=0+10+21=31 18
18 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*1 + 7*2 = 0 + 10 + 14 = 24 < 30 W=0 P=1 C=2 Obj: 15W + 10P + 7C Current Best: 0 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*1 + 7*3 = 0 + 10 + 21 = 31 W=0 P=1 C=3 Obj: 15W + 10P + 7C Current Best: 0 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30
Basic Branch Bound 0bj:15W+102+7C 4W+3P+2C≤9 Current Best:31 15W+10P+7C230 W=0 P=1 15*0+10*1+7*3=0+10+21=31 Since obj current best value,current value is updated to 31. Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:31 15W+10P+7C≥30 W=0 15*0+10*2+7*max(C)=0+20+28=48 19
19 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*1 + 7*3 = 0 + 10 + 21 = 31 W=0 P=1 C=3 Obj: 15W + 10P + 7C Current Best: 31 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30 Since obj > current best value, current value is updated to 31. MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*2 + 7*max(C) = 0 + 20 + 28 = 48 W=0 P=2 Obj: 15W + 10P + 7C Current Best: 31 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30
Basic Branch Bound 0b:15W+10P+7C 4w+3P+2C≤9 Current Best:31 15W+10P+7C≥30 W=0 15*0+10*2+7*maX(C)=0+20+28=48 The subtree of Cz2(in green)is pruned,since 4*0+3*2+2*2>9. Now,max(C)=1. Basic Branch Bound 0bj:15W+10P+7C 4W+3P+2C≤9 Current Best:31 15W+10P+7C≥30 W=0 2 15*0+10*2+7*max(C)=0+20+7=27 Since maximum possible obj is smaller than the current best value,the subtree C=0 and C=1 are pruned. 20
20 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*2 + 7*max(C) = 0 + 20 + 28 = 48 W=0 P=2 The subtree of C ≥ 2 (in green) is pruned, since 4*0+3*2+2*2 > 9. Now, max(C) = 1. Obj: 15W + 10P + 7C Current Best: 31 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30 MSC Seminar (January 30, 2012) Basic Branch & Bound 15*0 + 10*2 + 7*max(C) = 0 + 20 + 7 = 27 W=0 P=2 Since maximum possible obj is smaller than the current best value, the subtree C=0 and C=1 are pruned. Obj: 15W + 10P + 7C Current Best: 31 4W + 3P + 2C ≤ 9 15W + 10P + 7C ≥ 30