A heuristic for mixed linear integer bi-level programming problems based on benders decomposition
Author
Codina, E.; Lopez, F.
Type of activity
Presentation of work at congresses
Name of edition
1st International Workshop on Bi-level Programming
Date of publication
2017
Presentation's date
2016-03-10
Book of congress proceedings
1st International Workshop on Bi-level Programming (IWOBIP 2016): Nuevo Leon, Mexico: march 7-11, 2016: proceedings
First page
1
Last page
1
Project funding
ROBUSTEZ, RECUPERACION Y ADAPTABILIDAD DE SISTEMAS DE TRANSPORTE PUBLICO
Abstract
In this paper, a heuristic algorithm for a subclass of mixed-integer linear bi-level programming problem (MILBP) is presented. This subclass covers all MILBPs in which the upper level problem may contain both integer and continuous variables and variables for the lower level are continuous. The algorithm can be considered as a direct extension of the classical Benders decomposition method for linear integer programming. Although other Benders extensions have been previously used to solve these k...
In this paper, a heuristic algorithm for a subclass of mixed-integer linear bi-level programming problem (MILBP) is presented. This subclass covers all MILBPs in which the upper level problem may contain both integer and continuous variables and variables for the lower level are continuous. The algorithm can be considered as a direct extension of the classical Benders decomposition method for linear integer programming. Although other Benders extensions have been previously used to solve these kinds of problems, the presented extension shows remarkable differences and advantages compared with other extensions. This analysis shows that the algorithm always finds a feasible solution, although it might be trapped in a local optima. The algorithm is applied to the Design of a Rapid Transit Network considering competition between two modes of transportation: rapid transit transport and private car. A new and consistent formulation of this problem in which the modal choice is modeled using entropy functions which are evaluated in the lower level. The upper level carries out the design of the Rapid Transit Network according to the demand that want to use this mode of transportation. Results are reported on two test networks showing the utility of the algorithm.