An Example of Benders Decomposition
John Mitchell

Consider the mixed integer programming problem (MIP):

max    8x     +9x      +5x      +6x     -  15y     - 10y
           1        2       3        4          1         2
s.t.     x1             +x3                                  ≤   1

         x1                      +x4                         ≤   1

                  x2    +x3                                  ≤   1

                  x2             +x4                         ≤   1
                                           -  y       - y    ≤   -  1
                                                1         2
         x                                 -  y              ≤   0
           1                                    1
                  x2                       -  y1             ≤   0

                           x3                         - y2   ≤   0

                                   x4                 - y2   ≤   0

                                   xj                        ≥   0    ∀j
                                                         y       binary      ∀i
                                                          i

Solve this problem using Bender’s decomposition.

Format:

max            cT x   +   dT y

subject   to    Ax    +   H  y   ≤   b

                  x              ≥   0

                             y       binary

Solution:

Initial Revised Master Problem:

max    z   - 15y1    - 10y2
s.t    z                       ≤    28

                           yi       binary

Solution to (RMP) is z = 28, y = (0, 0). Objective function for the subproblem is (b -HTy)Tu = bTu since y = 0. Subproblem is:

min            u    +   u    +    u   +    u    -   u
     u           1        2        3         4        5
subject   to   u1   +   u2                               +   u6                               ≥   8

                                  u3  +    u4                     +    u7                     ≥   9         (SP   )

               u1            +    u3                                        +   u8            ≥   5

                        u2            +    u4                                        +   u9   ≥   6

                                                                                          u   ≥   0

Solution is unbounded, with a ray r1 = (0, 0, 0, 0, 1, 0, 0, 0, 0)T.

Add constraint (r1)THy bTr1 to (RMP):

max    z   -   15y1    -   10y2

s.t    z                           ≤    28

           -      y1   -      y2   ≤    - 1

                               yi       binary

Solution is y = (0, 1), z = 28, with value 18. Updated subproblem with objective (b -HTy)Tu is:

minu           u1   +   u2   +    u3  +    u4                         +   u8   +   u9

subject   to   u1   +   u2                          +   u6                              ≥    8

                                  u3  +    u4                +   u7                     ≥    9        (SP   )
               u             +    u                                   +   u             ≥    5
                 1                 3                                        8
                        u2            +    u4                                  +   u9   ≥    6

                                                                                     u  ≥    0

Optimal value is 11 < z . One solution is u1 = (0, 0, 0, 0, 0, 8, 9, 5, 6)T.

Add constraint z + (u1)THy bTu1 to (RMP):

max    z   -   15y1    -   10y2

s.t    z                           ≤    28

           -      y1   -      y2   ≤    - 1

       z   -   17y1    -   11y2    ≤    0
                               y        binary
                                i

Solution is y = (1, 1), z = 28, with value 3. Updated subproblem with objective (b -HTy)Tu is:

minu           u1   +   u2   +    u3  +    u4   +   u5   +   u6   +   u7   +    u8   +   u9

subject   to   u1   +   u2                               +   u6                               ≥   8
                                  u   +    u                      +   u                       ≥   9         (SP   )
                                   3         4                          7
               u1            +    u3                                       +    u8            ≥   5

                        u2            +    u4                                        +   u9   ≥   6

                                                                                          u   ≥   0

Optimal value is 17 < z . One solution is u2 = (8, 0, 0, 9, 0, 0, 0, 0, 0)T.

Add constraint z + (u2)THy bTu2 to (RMP):

max    z   -   15y1    -   10y2

s.t    z                           ≤    28

           -      y1   -      y2   ≤    - 1

       z   -   17y1    -   11y2    ≤    0
       z                           ≤    17

                               yi       binary

Solution is y = (1, 0), z = 17, with value 2. Updated subproblem with objective (b -HTy)Tu is:

minu           u1   +   u2   +    u3  +    u4       +   u6   +   u7
subject   to   u    +   u                           +   u                               ≥    8
                 1        2                               6
                                  u3  +    u4                +   u7                     ≥    9        (SP   )

               u1            +    u3                                  +   u8            ≥    5

                        u2            +    u4                                  +   u9   ≥    6

                                                                                     u  ≥    0

Optimal value is 17 = z . The point u2 is still optimal to the subproblem. So we have the optimal solution to the master problem, namely y = (1, 0) with z = 17. Fixing this choice of y in the original (MIP) gives the solution x = (8, 9, 0, 0), which is the x portion of the optimal solution. The optimal value is indeed 2.