# 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

**URI:** https://alfresco.uclouvain.be/alfresco/service/guest/streamDownload/workspace/SpacesStore/0f8e2eec-b77e-40a4-af87-b1a5a738e696/coredp2019_20web.pdf?guest=true

### 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

### 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