Solving Integer Programming with Branch-and-Bound …

1 Solving Integer Programming with Branch-and-Bound TechniqueThis is the divide and conquer method. We divide a large problem into a few smaller ones. (This is the branch part.) The conquering part is done by estimate how good a solution we can get for each smallerproblems (to do this, we may have to divide the problem further, until we get a problem that we can handle),that is the bound will use thelinear Programming relaxationto estimate the optimal solution of an Integer Programming .* For an Integer Programming modelP, the linear Programming model we get by dropping the require-ment that all variables must be integers is called the linear Programming relaxation steps are: Divide a problem into subproblems Calculate the LP relaxation of a subproblem The LP problem has no feasible solution, done; The LP problem has an Integer optimal solution;done.

2 Compare the optimal solution with thebest solution we know (the incumbent). The LP problem has an optimal solution that is worse than the incumbent, all the cases above, we know all we need to knowabout that subproblem. We say that subproblemis fathomed. The LP problem has an optimal solution that are not all Integer , better than the incumbent. Inthis case we would have to divide this subproblem further and 1 MaxZ= x1+4x2 Subject to 10x1+20x2 225x1+10x2 49x1 5xi 0,xi s are integers-101234-1123456( ,3)1 For the LP relaxationMaxZ= x1+4x2s. t. 10x1+20x2 225x1+10x2 49x1 5xi 0 Optimal solution of the relaxation is( ,3)withz= Then we consider two cases:x1 4andx1 3. 10x1+20x2=226543210-143210-131=x41=xThe linear Programming relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 49x1 5x1 4x2 0has optimal solution at(4, )withZ= (4, )2 The linear Programming relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 494 x1 5x2 3has no feasible solution(5x1+10x2 50)so the IP has no feasible solution linear Programming relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 494 x1 50 x2 2has an optimal solution at(4,2)withZ=4.

3 This is the optimal solution of the IP as well. Currently, thebest value ofZfor the original IP isZ= (4,2)Now we consider the branch of0 x1 3. The LP relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 49x1 30 xi3has an optimal solution at(3, )withZ= We branch out further to two cases:x2 2andx2 (3, )4=ZThe LP relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 49x1 3x2 3has no feasible solution( 10x1+20x2 30). The IP has no solution either. The LP relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 490 x1 30 x2 2has an optimal at( ,2)withZ= ( , 2)4=Z4We branch further with two cases:x1 2orx1 1(we still have0 x2 2).6543210-143210-14=ZThe LP relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 492 x1 30 x2 2has an optimal at(2,2),withZ=6. Since this is better than the incumbentZ=4at(4,2), this new integersolution is our current best (2,2)6=ZThe LP relaxationMaxZ= x1+ 10x1+20x2 225x1+10x2 490 x1 10 x2 25has an optimal at(1, )withZ= the value ofZgreater This branch is (1, ) 2 Consider the following BIP problem:MaxZ=9x1+5x2+6x3+ +3x2+5x3+2x4 10x3+x4 1 x1+x3 0 x2+x4 0xiare binaryThe optimal solution of the LP relaxationMaxZ=9x1+5x2+6x3+ +3x2+5x3+2x4 10x3+x4 1 x1+x3 0 x2+x4 0xi 1for1 i 4xi 0has optimal solution at(5/6,1,0,1)withZ= 1:x1=0orx1= The problem becomesMaxZ=5x2+4x4 Subject to3x2+2x4 10 x2+x4 0xiare binary6 The optimal solution of the LP relaxation is at(1,1)withZ=9.

4 (Current best solution.) The LP relaxationMaxZ=9+5x2+6x3+ +5x3+2x4 4x3+x4 1x3 1 x2+x4 0xi 1for2 i 4xi 0has optimal solution at(1, ,0, )withZ= :x2=0orx2= LP relaxation (in this case we havex4=0as well)MaxZ=9+ 4x3 1x3 0has optimal solution at(1,0, ,0)withZ= :x3=0orx3= optimal solution is(1,0,0,0)withZ=9(not better than the current best solution). optimal solution of the LP relaxationMaxZ=14+6x3+ +2x4 1x3+x4 1x3 1x4 1xi 0is at(1,1,0, )withZ= previous optimal solution(1,1,0, )is still feasible therefore still (1,1,0,0)is (It becomes the current best solution.) (1,1,0,1)is not feasible the current best solution(1,1,0,0)withZ=14is the optimal (5/6,1,0,1)z= (0,1,0,1)z=9x_1 = 0(1, ,0, )z= (1,0, ,0)z= (1,1,0, )z=16(1,0,0,0)z=9No FSx_1 = 1x_2 = 0x_2 = 1x_3 = 0x_3 = 1(1,1,0, )z=16No FSx_3 = 0x_3 = 1(1,1,0,0)z=14(1,1,0,1)Notfeasiblex_4 = 0x_4 = 1 Rule of FathomingA subproblem is fathomed1.

5 The relaxation of the subproblem has an optimal solution withz<z wherez is the current bestsolution;2. The relaxation of the subproblem has no feasible solution;3. The relaxation of the subproblem has an optimal solution that has all Integer values (or all binary ifit is an BIP).8