论文标题
一种基于无参数分解的线性双层程序的新计算方法
A New Computational Approach for Solving Linear Bilevel Programs Based on Parameter-Free Disjunctive Decomposition
论文作者
论文摘要
线性双层程序（线性BLP）已在多种应用中广泛用于计算数学和优化。线性BLP的单层重新构造用其Karush-kuhn-tucker最佳条件代替了低级线性程序，并使用Big-M Technique将互补的松弛条件线性化。尽管该方法很简单，但它需要找到最近显示的计算是NP- hard的Big-M。本文提出了一种基于析取的分解算法，该算法不需要找到大型MS，而保证获得的解决方案是最佳的。我们的经验显示了我们算法的有希望的性能。
Linear bilevel programs (linear BLPs) have been widely used in computational mathematics and optimization in several applications. Single-level reformulation for linear BLPs replaces the lower-level linear program with its Karush-Kuhn-Tucker optimality conditions and linearizes the complementary slackness conditions using the big-M technique. Although the approach is straightforward, it requires finding the big-M whose computation is recently shown to be NP-hard. This paper presents a disjunctive-based decomposition algorithm which does not need finding the big-Ms whereas guaranteeing that obtained solution is optimal. Our experience shows promising performance of our algorithm.
