Benders' algorithm with (mixed)-integer subproblems

Weninger D, Wolsey L (2019)

Publication Language: English

Publication Status: Submitted

Publication Type: Other publication type

Future Publication Type: Journal article

Publication year: 2019



We consider problems of the form $\min\{cx+hy: Ax+By \geq b, x \in \Z^n_+,y \in Y \subseteq \R^p_+\}$ that are often 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$ 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.

Authors with CRIS profile

Involved external institutions

How to cite


Weninger, D., & Wolsey, L. (2019). Benders' algorithm with (mixed)-integer subproblems.


Weninger, Dieter, and Laurence Wolsey. Benders' algorithm with (mixed)-integer subproblems. 2019.

BibTeX: Download