论文标题
利用随机线性双利编程的多面体几何形状
Exploiting the polyhedral geometry of stochastic linear bilevel programming
论文作者
论文摘要
我们研究了线性折线编程问题，其低级目标由带有已知分布的随机成本向量给出。我们考虑了这种分布是非原子的情况，可以从萨拉斯（Salas）和斯文森（Svensson）（2023）的意义上使用贝叶斯（Bayesian）方法来重新制定领导者的问题，并以决策依赖性分布集中于追随者问题的可行集合的顶点。我们称其为顶点支持的信念。我们证明，这种公式是在可行的一组高点弛豫组的所谓腔室复合物上的分段仿射。我们提出了两种算法方法，以解决享受最后一次属性的一般问题。第一个是基于枚举腔室配合物的顶点。这种方法是不可扩展的，但我们将其作为计算基线及其理论利益表示。第二个是基于以下事实，即在全维室内的内部随机绘制的域躺着的点（概率1），其中问题（仅限于该腔室）可以减少到线性程序。最后，我们通过计算实验来评估这些方法，该实验显示了这两种方法的优势和挑战。
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 decision-dependent distribution that concentrates on the vertices of the feasible set of the follower's problem. We call this 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. This approach is not scalable, but we present it as a computational baseline and for its theoretical interest. 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.
