基于凹性割的线性双层规划全局优化算法

摘要

A concavity cut is defined by discussing the duality gap of the lower problem of the linear bilevel programming. Based on the feature of the concavity cut, a cutting plane algorithm for solving linear bilevel programming is given. Based on the result that a global optimal solution to linear bilevel programming occurs at an extreme point of its constraint region, the proposed algorithm can obtain a global optimal solution. Finally, a example is given to demonstrate the effectiveness of the algorithm.%通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法.由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性.