Benders Subproblem Decomposition for Bilevel Problems with Convex Follower

Geunyeong Byeon () and Pascal Van Hentenryck ()
Additional contact information
Geunyeong Byeon: School of Computing and Augmented Intelligence, Arizona State University, Tempe, Arizona 85281
Pascal Van Hentenryck: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2022, vol. 34, issue 3, 1749-1767

Abstract: Bilevel optimization formulates hierarchical decision-making processes that arise in many real-world applications, such as pricing, network design, and infrastructure defense planning. In this paper, we consider a class of bilevel optimization problems in which the upper level problem features some integer variables and the lower level problem enjoys strong duality. We propose a dedicated Benders decomposition method for solving this class of bilevel problems, which decomposes the Benders subproblem into two more tractable, sequentially solvable problems that can be interpreted as the upper and lower level problems. We show that the Benders subproblem decomposition carries over to an interesting extension of bilevel problems, which connects the upper level solution with the lower level dual solution, and discuss some special cases of bilevel problems that allow sequence-independent subproblem decomposition. Several novel schemes for generating numerically stable cuts, finding a good incumbent solution, and accelerating the search tree are discussed. A computational study demonstrates the computational benefits of the proposed method over a state-of-the-art, bilevel-tailored, branch-and-cut method; a commercial solver; and the standard Benders method on standard test cases and the motivating applications in sequential energy markets.

Keywords: bilevel optimization; hierarchical decision making; sequential market clearing; Benders decomposition; mixed-integer bilevel second-order cone programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1128 (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:orijoc:v:34:y:2022:i:3:p:1749-1767

Access Statistics for this article

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