Benders Decomposition for Discrete–Continuous Linear Bilevel Problems with application to traffic network design
Benders Decomposition for Discrete–Continuous Linear Bilevel Problems with application to traffic network design
复制标题
DOI：
10.1016/j.trb.2014.09.007
复制
发表时间：
2014-12
影响因子：
6.8
通讯作者：
P. Fontaine;S. Minner
中科院分区：
文献类型：
--
作者：
P. Fontaine;S. Minner
在部分合作假设下，提出了一种新的具有二元领导变量和连续从变量的线性双层问题的快速求解方法。利用Karush-Kuhn-Tucker条件将双层问题转化为单层问题。这个非线性模型可以线性化，因为二进制领导决策变量实现的特殊结构，并随后通过Benders分解算法求解到全局最优。我们说明了离散网络设计问题的方法，增加弧现有的道路网络在领导者阶段，并预计后续阶段的交通平衡的能力。由于该问题的目标函数是非线性的，我们采用了基于连续变量的线性化方法来处理增函数、凸函数和非线性函数。数值试验表明，该算法可以解决甚至大的两层问题的情况下。
We propose a new fast solution method for linear Bilevel Problems with binary leader and continuous follower variables under the partial cooperation assumption. We reformulate the Bilevel Problem into a single-level problem by using the Karush–Kuhn–Tucker conditions. This non-linear model can be linearized because of the special structure achieved by the binary leader decision variables and subsequently solved by a Benders Decomposition Algorithm to global optimality. We illustrate the capability of the approach on the Discrete Network Design Problem which adds arcs to an existing road network at the leader stage and anticipates the traffic equilibrium for the follower stage. Because of the non-linear objective functions of this problem, we use a linearization method for increasing, convex and non-linear functions based on continuous variables. Numerical tests show that this algorithm can solve even large instances of Bilevel Problems.