Abstract
We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to pose the problem of the leader using vertex-supported beliefs in the sense of [29]. We prove that, under suitable assumptions, this formulation turns out to be piecewise affine over the so-called chamber complex of the feasible set of the high point relaxation. We propose two algorithmic approaches to solve general problems enjoying this last property. The first one is based on enumerating the vertices of the chamber complex. The second one is a Monte-Carlo approximation scheme based on the fact that randomly drawn points of the domain lie, with probability 1, in the interior of full-dimensional chambers, where the problem (restricted to this chamber) can be reduced to a linear program.
The first author was supported by FONDECYT Iniciación 11190515 (ANID-Chile). The second author was supported by the Center of Mathematical Modeling (CMM) FB210005 BASAL funds for centers of excellence (ANID-Chile), and the grant FONDECYT Iniciación 11220586 (ANID-Chile). The third author was supported by the grant FONDECYT postdoctorado 3210735 (ANID-Chile).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The last two entries of Table 1 correspond to cases where \(\mathscr {F}_{\le {n_x}}\) was not fully computed due to the time limit.
References
Coral bilevel optimization problem library. https://coral.ise.lehigh.edu/data-sets/bilevel-instances/ Accessed 3 Nov 2022
Bazaraa, M.S., Sherali, H.D., Shetty, C. M.: Nonlinear programming: theory and algorithms. John Wiley Sons (2013)
Beck, Y., Ljubić, I., Schmidt, M.: A survey on bilevel optimization under uncertainty. European J. Oper. Res., (2023) (In Press)
Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: A fresh approach to numerical computing. SIAM review 59(1), 65–98 (2017)
Buchheim, C., Henke, D., Irmai, J.: The stochastic bilevel continuous knapsack problem with uncertain follower’s objective. J. Optim. Theory. Appl. 194, 521–542 (2022)
Burtscheidt, J., Claus, M.: Bilevel Linear Optimization Under Uncertainty. In: Dempe, S., Zemkoho, A. (eds.) Bilevel Optimization. SOIA, vol. 161, pp. 485–511. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-52119-6_17
Claus, M.: On continuity in risk-averse bilevel stochastic linear programming with random lower level objective function. Oper. Res. Lett. 49(3), 412–417 (2021)
Claus, M.: Existence of solutions for a class of bilevel stochastic linear programs. European J. Oper. Res. 299(2), 542–549 (2022)
De Loera, J., Rambau, J., Santos, F.: Triangulations: structures for algorithms and applications, volume 25. Springer Science Business Media (2010) https://doi.org/10.1007/978-3-642-12971-1
Dempe, S.: Foundations of bilevel programming. Springer Science Business Media (2002) https://doi.org/10.1007/b101970
Dempe, S., Kalashnikov, V., Pérez-Valdés, G.A., Kalashnykova, N.: Bilevel programming problems. Energy Systems. Springer, Heidelberg, 2015. Theory, algorithms and applications to energy networks https://doi.org/10.1007/978-3-662-45827-3
Dempe, S., Zemkoho, A. (eds.): SOIA, vol. 161. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-52119-6
Forcier, M.: Multistage stochastic optimization and polyhedral geometry. PhD. Thesis, École de Ponts - ParisTech (2022)
Forcier, M., Gaubert, S., Leclère, V.: Exact quantization of multistage stochastic linear problems (2021) (preprint - arXiv:2107.09566)
Gawrilow, E., Joswig, M., polymake: a framework for analyzing convex polytopes. In Polytopes–combinatorics and computation of DMV Sem (Oberwolfach, 1997), 29, pp. 43–73. Birkhäuser, Basel, (2000)
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual (2022)
Hiriart-Urruty, J.-B., Lemaréchal, J.-B.: Convex analysis and minimization algorithms I: Fundamentals, volume 305. Springer science business media (2013) https://doi.org/10.1007/978-3-662-02796-7
Homem-de Mello, T., Bayraksan, G.: Monte Carlo sampling-based methods for stochastic optimization. Surv. Oper. Res. Manag. Sci., 19(1), 56–85 (2014)
Ivanov, S.V.: A bilevel programming problem with random parameters in the follower’s objective function. Diskretn. Anal. Issled. Oper. 25(4), 27–45 (2018)
Khachiyan, L., Boros, E., Borys, K., Gurvich, V., Elbassioni, K.:Generating all vertices of a polyhedron is hard. In 20th Anniversary Volume, 1–17. Springer (2009) https://doi.org/10.1007/s00454-008-9050-5
Kleinert, T., Labbé, M., Ljubić, I., Schmidt, M.: A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9, 100007 (2021)
Klenke, A: Probability Theory: a Comprehensive Course. Springer (2014) https://doi.org/10.1007/978-1-4471-5361-0
Leobacher, G., Pillichshammer, F.: Introduction to quasi-Monte Carlo integration and applications. Compact Textbooks in Mathematics. Birkhäuser/Springer, Cham (2014)
Lu, S., Robinson, S.M.: Normal fans of polyhedral convex sets: structures and connections. Set-Valued Anal. 16(2–3), 281–305 (2008)
Mak, W.-K., Morton, D.P., Wood, R.K.: Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper. Res. Lett. 24(1–2), 47–56 (1999)
Mallozzi, L., Morgan, J.: Hierarchical Systems with Weighted Reaction Set, pp. 271–282. Springer, US, Boston, MA, (1996) https://doi.org/10.1007/978-1-4899-0289-4_19
Muñoz, G., Salas, D., Svensson, A.: Exploiting the polyhedral geometry of stochastic linear bilevel programming (2023). (preprint - arXiv:2211.02268. Former title: Linear bilevel programming with uncertain lower-level costs)
Rambau, J., Ziegler, G.M.: Projections of polytopes and the generalized baues conjecture. Discrete Comput. Geom. 16(3), 215–237 (1996)
Salas, D., Svensson, A.: Existence of solutions for deterministic bilevel games under a general bayesian approach (2020) (preprint - arXiv:2010.05368)
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on stochastic programming–modeling and theory, volume 28 of MOS-SIAM Series on Optimization. 3rd eds Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, (2021)
Stackelberg, V.H.: Marktform und Gleichgewitch. Springer (1934) https://doi.org/10.1007/978-3-642-12586-7
Zhou, S., Zemkoho, A.B., Tin, A.: BOLIB: Bilevel Optimization LIBrary of Test Problems. In: Dempe, S., Zemkoho, A. (eds.) Bilevel Optimization. SOIA, vol. 161, pp. 563–580. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-52119-6_19
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Muñoz, G., Salas, D., Svensson, A. (2023). Exploiting the Polyhedral Geometry of Stochastic Linear Bilevel Programming. In: Del Pia, A., Kaibel, V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2023. Lecture Notes in Computer Science, vol 13904. Springer, Cham. https://doi.org/10.1007/978-3-031-32726-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-031-32726-1_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-32725-4
Online ISBN: 978-3-031-32726-1
eBook Packages: Computer ScienceComputer Science (R0)