Benders’ algorithm with (mixed)-integer subproblems

Dieter, Weninger () and Laurence, Wolsey, ()
Additional contact information
Dieter, Weninger: FAU Erlangen-Nürnberg
Laurence, Wolsey,: Université catholique de Louvain, CORE, Belgium

No 2019020, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Keywords: Benders’ algorithm; mixed-integer subproblems; branch-and-cut; value function (search for similar items in EconPapers)
JEL-codes: H20 H31 H50 (search for similar items in EconPapers)
Date: 2019-11-18
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2019.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2019020

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().