Benders Decomposition for Discrete–Continuous Linear Bilevel Problems with application to traffic network design |
| |
| Institution: | 1. Transportation Management College, Dalian Maritime University, Dalian 116026, PR China;2. School of Automotive Engineering, Dalian University of Technology, Dalian 116024, PR China;3. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, PR China;1. School of Civil and Environmental Engineering, Nanyang Technological University, 50 Nanyang Avenue, 639798, Singapore;2. Department of Civil Engineering, The University of Hong Kong, Pok Fu Lam, Hong Kong;1. Industrial Engineering Department - Pontifícia Universidade Católica do Rio de Janeiro, Rua Marquês de São Vicente, 225, Gávea - Rio de Janeiro, RJ 22451-900, Brazil;2. Chemical Engineering Department - Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA 15213, USA |
| |
| Abstract: | 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. |
| |
| Keywords: | Bilevel Programming Discrete Network Design Problem Benders Decomposition Linear approximation |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
