% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@misc{faucris.229318862,
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.