Linear Optimization in Applications

6. Integer Programming Solution

The most powerful method of finding solutions for integer linear programming problems is the branch and bound method. In this chapter, we will consider two examples using the branch and bound method. One example is a problem with decision variables greater than zero but which must be integers. Another example is a problem with zero-one variables. 6.1 An Example 01 Integer Linear Programming Solutioning Example6.1 Solve, using the branch and bound method, the following integer linear programming model: Max Z = 6Xl + 8X2 subject to 2Xl + X2 三 6 2Xl + 3X2 三 9 Xl , X2 ;;::: 0 and integers Solution 6. 1 There are 4 steps in solving the model 品且i First of all, solve the model as if Xl and X2 are 且且 restricted to be integers. We call this problem 1 (or P1): Max Z = 6Xl + 8X2 subject to 2Xl + X2 三 6 2Xl + 3X2 三 9 X}, X2 三 O The optimal solution, found by the simplex method or the graphical method (see Fig. 6.1), of Pl is: ，因 Z = 25.5 Xl = 2.25 X2 = 1.5 1.5) Unear Optimization in Apρ 曲你開S Fig.6.1 Graphical solution of Pl Since Xl and X2 割草 not integers. we must go to step 2 缸且主 Divide Pl inlo two problems, p2 and P3 、Ne branch on X2 by adding the bound Xz :S; 1 10 Pl fonnir苟且， and adding the bound Xz 主 2 to P I forming P3. The branching variable X1 is chosen because it is less near 10 an înteger 山an XI. The following shows the two branched and bound problems p2 and P3 也 fl Max Z =6Xl + 8X2 MaxZ =6xI + 8X2 subj回tto '"剛回tto 2耳 1 + X1 :s; 6 2xI + X2 :s; 6 2xI + 3X2 :s; 9 2xI + 3X2 :s; 9 X2 :S; I "注 2 XI , X2 2!: 0 XI, X2 2!: 0 As a result of the branch 曲d bound, the feasîble spaces for p2 and P3 are separaled out from Ihe original feasible space of P1, as shown in Fig. 6.2 Integer Programming So/ution 107 X2 Xl Fig. 6.2 Feasible spaces of P2 and P3 The optimal solutions, found by the simplex method or the graphical method, of P2 and P3 are: P2 Z = 23 Xl = 2.5 X2 = 1 fJ Z = 25 Xl = 1.5 X2 = 2 We can see that the solutions of P2 and P3, although still not all integers, are c10ser to what we want after the first branch and bound. The branch and bound process intentionally changes the non-integral X2 of Pl into an integer. Usually, we use a tree diagram to represent the branch and bound process as shown in Fig. 6.3. 108 Linear Optimization in Applications 7 、;2 Fig. 6.3 Tree diagram for branch and bound process (a) Now, we go to step 3. 品且主 Since neither P2 nor P3 has an all-integer solution, we have to do further branching. We now face the question of which one we should branch first, P2 or P3? The answer is easy. Since the Z value of P3 (i.e. 25) is larger than that of P2 (i.e. 23), we branch P3 first as it has a higher chance of obtaining an allinteger solution with 1缸ger Z than P2. So, we divide P3 into two problems, P4 and P5. This time, we branch on x1 by adding the bounds x1 ~ 1 and x1 ~ 2 to P3 forming P4 and P5 respectively as follows: E是 E三 Max Z = 6x1 + 8X2 Max Z = 6Xl + 8X2 subject to subject to 2Xl + X2 三 6 2Xl + X2 ~ 6 2Xl + 3X2 三 9 2Xl + 3X2 ~ 9 X2 ~ 2 X2 ~ 2 Xl 三 1 Xl ~ 2 Xl , X2 ~ 0 Xl, X2 ~ 0 Integer Programming Solution 109 The optimal solutions, found by the simplex method, of P4 and P5 缸e: E是 E三 Z = 24.67 No feasible solution Xl = X2 = 2.33 P5 has no feasible solution. To denote t 由 hi 臼 s， we put a "T" sign is seen, we know that the branch is terminated there, as shown in Fig. 6.4. 、 、三2 T Fìg.6.4 Tree dìagram for branch and bound process (b) Now we have to tackle the two remaining problems, P2 and P4. Which one should we tackle first? The answer is of course P4 because the Z value for P4 (i.e. 24...