On Bilevel Optimization with Inexact Follower

M. Hosein Zare (), Oleg A. Prokopyev () and Denis Sauré ()
Additional contact information
M. Hosein Zare: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Oleg A. Prokopyev: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Denis Sauré: Department of Industrial Engineering, University of Chile, 8370456 Santiago, Chile

Decision Analysis, 2020, vol. 17, issue 1, 74-95

Abstract: Traditionally, in the bilevel optimization framework, a leader chooses her actions by solving an upper-level problem, assuming that a follower chooses an optimal reaction by solving a lower-level problem. However, in many settings, the lower-level problems might be nontrivial, thus requiring the use of tailored algorithms for their solution. More importantly, in practice, such problems might be inexactly solved by heuristics and approximation algorithms. Motivated by this consideration, we study a broad class of bilevel optimization problems where the follower might not optimally react to the leader’s actions. In particular, we present a modeling framework in which the leader considers that the follower might use one of a number of known algorithms to solve the lower-level problem, either approximately or heuristically. Thus, the leader can hedge against the follower’s use of suboptimal solutions. We provide algorithmic implementations of the framework for a class of nonlinear bilevel knapsack problem (BKP), and we illustrate the potential impact of incorporating this realistic feature through numerical experiments in the context of defender-attacker problems.

Keywords: bilevel optimization; hierarchical optimization; robust optimization; heuristics; defender-attacker problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/deca.2019.0392 (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:ordeca:v:17:y:2020:i:1:p:74-95

Access Statistics for this article

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