Benders’ algorithm with (mixed)-integer subproblems

We consider problems of the form min{cx + hy: Ax + By ≥ b, x \in Z^n_+, y \in Y \subseteq R^p_+} that are foten treated using Benders' algorithm, but in which some of the y-variables are required to be integer. We present two algorithms that hopefully add to and clarify some of the algorithms proposed since the year 2000. Both are branch-and-cut algorithms solving linear programs by maintaining a strict separation between a Master problem in (x,\eta)-variables and a subproblem in the y-variables. The first involves nothing but the solution of linear programs, but involves branching in (x,y)-space. It is demonstrated on a small capacitated facility location problem with single-sourcing. The second restricted to problems with x \in {0,1}n n only requires branching in the x-space, but uses cutting planes in the subproblem based on the integrality of the y-variables that are converted/lifted into valid inequalities for the original problem in (x,y)-variables. For the latter algorithm we show how the lifting can be carried out trivially for several classes of cutting planes. A 0-1 knapsack problem is provided as an example. To terminate we consider how the information generated in the course of the algorithms can be used to carry out certain post-optimality analysis.