Journal
JOURNAL OF GLOBAL OPTIMIZATION
Volume 44, Issue 1, Pages 29-51Publisher
SPRINGER
DOI: 10.1007/s10898-008-9291-0
Keywords
Bi-level optimization; Mixed integer linear programming; Benders decomposition; Active constraints
Ask authors/readers for more resources
In this article, we propose a new algorithm for the resolution of mixed integer bi-level linear problem (MIBLP). The algorithm is based on the decomposition of the initial problem into the restricted master problem (RMP) and a series of problems named slave problems (SP). The proposed approach is based on Benders decomposition method where in each iteration a set of variables are fixed which are controlled by the upper level optimization problem. The RMP is a relaxation of the MIBLP and the SP represents a restriction of the MIBLP. The RMP interacts in each iteration with the current SP by the addition of cuts produced using Lagrangian information from the current SP. The lower and upper bound provided from the RMP and SP are updated in each iteration. The algorithm converges when the difference between the upper and lower bound is within a small difference epsilon. In the case of MIBLP Karush-Kuhn-Tucker (KKT) optimality conditions could not be used directly to the inner problem in order to transform the bi-level problem into a single level problem. The proposed decomposition technique, however, allows the use of KKT conditions and transforms the MIBLP into two single level problems. The algorithm, which is a new method for the resolution of MIBLP, is illustrated through a modified numerical example from the literature. Additional examples from the literature are presented to highlight the algorithm convergence properties.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available