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
Abstract
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
Belgium (BE)How to cite
APA:
Weninger, D., & Wolsey, L. (2019). Benders' algorithm with (mixed)-integer subproblems.
MLA:
Weninger, Dieter, and Laurence Wolsey. Benders' algorithm with (mixed)-integer subproblems. 2019.
BibTeX: Download