Exploiting the polyhedral geometry of stochastic linear bilevel programming

DOI10.1007/978-3-031-32726-1_26MaRDI QIDQ6086014zbMATH OpenOpenAlexFDO

Authors Gonzalo Muñoz, David Salas, Anton Svensson

Publication date 9 November 2023

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.02268

zbMATH Keywords

Bayesian approachbilevel programmingchamber complexenumeration algorithmMonte-Carlo algorithm

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Stochastic programming (90C15) Nonlinear programming (90C30) Hierarchical games (including Stackelberg games) (91A65)

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 reformulate the problem of the leader using the Bayesian approach in the sense of Salas and Svensson (2023) with a vertex-supported belief. We prove that this formulation is 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. Finally, we evaluate these methods through computational experiments showing both approaches' advantages and challenges.

Recommendations

• Bilevel linear optimization under uncertainty
• Risk-averse models in bilevel stochastic linear programming
• On a stochastic bilevel programming problem
• Sample approximations of bilevel stochastic programming problems with probabilistic and quantile criteria
• Bilevel stochastic linear programming problems with quantile criterion

Cites work

• A Bilevel Stochastic Programming Problem with Random Parameters in the Follower’s Objective Function
• A survey on bilevel optimization under uncertainty
• A survey on mixed-integer programming techniques in bilevel optimization
• Bilevel linear optimization under uncertainty
• Bilevel optimization. Advances and next challenges
• Bilevel programming problems. Theory, algorithms and applications to energy networks
• BOLIB: bilevel Optimization LIBrary of test problems
• Existence of solutions for a class of bilevel stochastic linear programs
• Foundations of bilevel programming
• Generalized adaptive partition-based method for two-stage stochastic linear programs: geometric oracle and analysis
• Generating all vertices of a polyhedron is hard
• scientific article; zbMATH DE number 417962 (Why is no real title available?)
• scientific article; zbMATH DE number 1552033 (Why is no real title available?)
• scientific article; zbMATH DE number 7005721 (Why is no real title available?)
• Introduction to quasi-Monte Carlo integration and applications
• Julia: a fresh approach to numerical computing
• Lectures on stochastic programming. Modeling and theory
• Monte Carlo bounding techniques for determinig solution quality in stochastic programs
• Normal fans of polyhedral convex sets
• On continuity in risk-averse bilevel stochastic linear programming with random lower level objective function
• polymake: a framework for analyzing convex polytopes
• Probability theory. A comprehensive course
• Projections of polytopes and the generalized Baues conjecture
• The stochastic bilevel continuous knapsack problem with uncertain follower's objective
• Triangulations. Structures for algorithms and applications

Cited in

(1)

• Exploiting the polyhedral geometry of stochastic linear bilevel programming

This page was built for publication: Exploiting the polyhedral geometry of stochastic linear bilevel programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6086014)