Enhancing the solution method of linear Bi – level programming problem based on enumeration method and dual method

Document Type : Original Paper

Authors

1 Department of Industrial Engineering, University of Kurdistan

2 Payamenur University of Tehran, Department of Mathematics

3 Department of Power Engineering, University of Kurdistan

Abstract

In the recent years, the bi-level programming problem (BLPP) is known as an appropriate approach for solving the real problems in applicable areas such as traffic, transportation, economics and supply chain management. There are several known algorithms to solve BLPP as an NP-hard problem. Almost all proposed algorithms in references have been used the Karush-Kuhn–Tucker to convert the BLPP into the single level problem which the obtained problem is complicated. In this paper, we attempt to develop two effective approaches, one based on enumeration method and the other based on duality characteristic for solving the linear BLPP. In these approaches, the BLPP is solved without using the Karush-Kuhn–Tucker conditions. The presented approaches achieve an efficient and feasible solution in an appropriate time which has been evaluated by comparing to references and test problems.

Keywords

Main Subjects

Full Text

References

[1] Bard, J.F. (1991). Some properties of the bi-level linear programming, Journal of Optimization Theory and Applications, 68, 371–378. [2] Mathieu, R., Pittard, L. and Anandalingam, G. (1994). Genetic algorithm based approach to bi-level Linear Programming, Operations Research, 28, 1–21. [3] L. Vicente, L., Savard, G. and Judice, J. (1994). Descent approaches for
quadratic bi-level programming, Journal of Optimization Theory and Applications, 81, 379–399. [4] Wang, G., Jiang, B. and Zhu,
K. (2010). Global convergent algorithm for the bi-level linear fractional-linear programming based on modified convex simplex method, Journal of Systems Engineering and Electronics, 21, 239–243. [5] Yibing, Lv., Tiesong, Hu., Guangmin, Wang. and Zhongping, Wan (2007). A penalty function method Based on Kuhn–Tucker condition for solving linear bi-level programming,
Applied Mathematics and Computation, 188, 808–813. [6] Zhongping, W. and Guangmin, W. (2011). A Dual-Relax Penalty
Function Approach for Solving Non- Linear Bi-Level Programming with Linear Lower Level Problem, Acta Mathematica Scientia, 31, 652–660. [7] Allende, G. B. and Still, G. (2012). Solving bi-level programs with the KKT-approach, Springer and Mathematical
Programming Society, 131, 37–48. [8] Dempe, S. and Zemkoho, A.B. (2012). On the Karush–Kuhn–Tucker reformulation of the
bi-level optimization problem, Nonlinear Analysis, 75, 1202–1218. [9] Arora, S.R. and Gupta, R. (2007). Interactive fuzzy goal
programming approach for bi-level programming problem, European Journal of Operational Research, 176, 1151–1166.

Files

History

  • Receive Date: 24 July 2014
  • Revise Date: 08 July 2015
  • Accept Date: 25 April 2015

Share

How to cite

Statistics