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. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.