Benders decomposition: working with several different submodels

Benders decomposition is a decomposition method for solving large Mixed Integer Programming problems. Instead of solving a MIP problem that may be too large for standard solution methods all-in-one, we work with a sequence of linear and pure integer subproblems (the latter with a smaller number of constraints than the original problem). The description of the decomposition algorithm below is taken from [Hu69] where the interested reader will also find proofs of its finiteness and of the statement that it always results in the optimal solution.

Consider the following standard form of a mixed-integer programming problem (problem I).

In the above, and all through this section, we use bold letters for vectors and matrices. For instance, Cx + Dy stands for ∑

For given values y' of y the problem above is reduced to a linear program (problem II)—we leave out the constant term in the objective:

The dual program of problem II is given by problem IId:

An interesting feature of the dual problem IId is that the feasible region of u is independent of y. Furthermore, from duality theory it follows that if problem IId is infeasible or has no finite optimum solution, then the original problem I has no finite optimum solution. Again from duality theory we know that if problem IId has a finite optimum solution u^* then this solution has the same value as the optimum solution to the primal problem (that is, u^*(b - By') = Cx^*), and for a solution u^p (at a vertex p of the feasible region) we have u^p(b - By') ≤ Cx^*. Substituting the latter into the objective of the original MIP problem we obtain a constraint of the form

To obtain the optimum solution z^* of the original MIP problem (problem I) we may use the following partitioning algorithm that is known as Benders decomposition algorithm:

Step 0

Find a u' that satisfies u'A ≤ C
if no such u' exists
then the original problem (I) has no feasible solution
else continue with Step 1
end-if

Step 1

Solve the pure integer program

minimize z
z ≥ u'(b - By) + Dy
y ≥ 0, y integer

If z is unbounded from below, take a z to be any small value z'.

Step 2

With the solution y' of Step 1, solve the linear program

maximize u(b - By')
uA ≤ C
u ≥ 0

If u goes to inifinity with u(b - By')
then add the constraint ∑_iu_i ≤ M, where M is a large positive constant, and resolve the problem
end-if
Let the solution of this program be u''.
if z' - Dy' ≤ u''(b - By')
then continue with Step 3
else return to Step 1 and add the constraint z' ≥ Dy + u''(b - By)
end-if

Step 3

With the solution y' of Step 1, solve the linear program

minimize Cx
Ax ≥ b - By'
x ≥ 0

x' and y' are the optimum solution z^* = Cx' + Dy'

This algorithm is provably finite. It results in the optimum solution and at any time during its execution lower and upper bounds on the optimum solution z^* can be obtained.