Decision Rule Approaches for Pessimistic Bilevel Linear Programs Under Moment Ambiguity with Facility Location Applications

Akshit Goyal (), Yiling Zhang () and Chuan He ()
Additional contact information
Akshit Goyal: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Yiling Zhang: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Chuan He: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455

INFORMS Journal on Computing, 2023, vol. 35, issue 6, 1342-1360

Abstract: We study a pessimistic stochastic bilevel program in the context of sequential two-player games, where the leader makes a binary here-and-now decision, and the follower responds with a continuous wait-and-see decision after observing the leader’s action and revelation of uncertainty. We assume that only the information regarding the mean, covariance, and support is known. We formulate the problem as a distributionally robust (DR) two-stage problem. The pessimistic DR bilevel program is shown to be equivalent to a generic two-stage distributionally robust stochastic (nonlinear) program with both a random objective and random constraints under proper conditions of ambiguity sets. Under continuous distributions, using linear decision rule approaches, we construct upper bounds on the pessimistic DR bilevel program based on (1) a 0-1 semidefinite programming (SDP) approximation and (2) an exact 0-1 copositive programming reformulation. When the ambiguity set is restricted to discrete distributions, an exact 0-1 SDP reformulation is developed, and explicit construction of the worst-case distribution is derived. To further improve the computation of the proposed 0-1 SDPs, a cutting-plane framework is developed. Moreover, based on a mixed-integer linear programming approximation, another cutting-plane algorithm is proposed. Extensive numerical studies are conducted to demonstrate the effectiveness of the proposed approaches on a facility location problem.

Keywords: pessimistic bilevel program; distributionally robust optimization; semidefinite program; copositive program; linear decision rules (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0168 (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:35:y:2023:i:6:p:1342-1360

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 ().