Perspectives on Using Benders Decomposition to Solve Two-Stage Stochastic Mixed-Integer Programs

Mike Hewitt () and Walter Rei ()
Additional contact information
Mike Hewitt: Loyola University Chicago
Walter Rei: Université du Québec à Montréal

A chapter in Combinatorial Optimization and Applications, 2024, pp 259-276 from Springer

Abstract: Abstract Benders decomposition has shown great potential as a means to efficiently solve two-stage stochastic integer programs. As originally proposed, the stochastic programs are decomposed by first partitioning the decision variables into two groups, separating the first-stage decisions, to define a master problem, from the second-stage decisions, to define a set of subproblems. An optimal solution to the stochastic program is then obtained by successively solving the master and subproblems, until the solution of the master can be established as optimal (the subproblems being used here as a means to find violated cuts to strengthen the master’s formulation). Although this decomposition strategy has produced successful results, recent studies have shown that the partitioning choices that underly the decomposition should be revisited. Specifically, the Benders method can be significantly enhanced and accelerated by either transferring information from the subproblems to the master, thus strengthening the latter’s formulation, or applying the reverse approach and sending information from the master to the subproblems, thus improving the quality of the cuts that can be obtained from them. In the present chapter, we thus highlight these new strategies to partition the decision variables and discuss how to successfully implement these enhancements for the Benders method.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:isochp:978-3-031-57603-4_12

Ordering information: This item can be ordered from
http://www.springer.com/9783031576034

DOI: 10.1007/978-3-031-57603-4_12

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().