A Converging Benders’ Decomposition Algorithm for Two-Stage Mixed-Integer Recourse Models

Niels van der Laan () and Ward Romeijnders ()
Additional contact information
Niels van der Laan: Department of Operations, University of Groningen, 9700 AV Groningen, Netherlands
Ward Romeijnders: Department of Operations, University of Groningen, 9700 AV Groningen, Netherlands

Operations Research, 2024, vol. 72, issue 5, 2190-2214

Abstract: We propose a new solution method for two-stage mixed-integer recourse models. In contrast to existing approaches, we can handle general mixed-integer variables in both stages. Our solution method is a Benders’ decomposition, in which we iteratively construct tighter approximations of the expected second stage cost function using a new family of optimality cuts. We derive these optimality cuts by parametrically solving extended formulations of the second stage problems using deterministic mixed-integer programming techniques. We establish convergence by proving that the optimality cuts recover the convex envelope of the expected second stage cost function. Finally, we demonstrate the potential of our approach by conducting numerical experiments on several investment planning and capacity expansion problems. Funding: The research of W. Romeijnders has been supported by the Netherlands Organisation for Scientific Research [Grant 451-17-034 4043].

Keywords: Optimization; stochastic programming; mixed-integer recourse; Benders’ decomposition (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2223 (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:inm:oropre:v:72:y:2024:i:5:p:2190-2214

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().