An Example of Benders Decomposition
John Mitchell

Consider the mixed integer programming problem (MIP): Solve this problem using Bender’s decomposition.

Format: Solution:

Initial Revised Master Problem: Solution to (RMP) is = 28, = (0, 0). Objective function for the subproblem is (b -HTy)Tu = bTu since y = 0. Subproblem is: Solution is unbounded, with a ray r1 = (0, 0, 0, 0, 1, 0, 0, 0, 0)T.

Add constraint (r1)THy bTr1 to (RMP): Solution is = (0, 1), = 28, with value 18. Updated subproblem with objective (b -HTy)Tu is: Optimal value is 11 < . One solution is u1 = (0, 0, 0, 0, 0, 8, 9, 5, 6)T.

Add constraint z + (u1)THy bTu1 to (RMP): Solution is = (1, 1), = 28, with value 3. Updated subproblem with objective (b -HTy)Tu is: Optimal value is 17 < . One solution is u2 = (8, 0, 0, 9, 0, 0, 0, 0, 0)T.

Add constraint z + (u2)THy bTu2 to (RMP): Solution is = (1, 0), = 17, with value 2. Updated subproblem with objective (b -HTy)Tu is: Optimal value is 17 = . The point u2 is still optimal to the subproblem. So we have the optimal solution to the master problem, namely = (1, 0) with = 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.