×

A new approach for solving linear bilevel problems using genetic algorithms. (English) Zbl 1135.90023

Summary: Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.

MSC:

90C05 Linear programming

Keywords:

extreme point

Software:

Genocop
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anandalingam, G.; Mathieu, R.; Pittard, C. L.; Sinha, N., Artificial intelligence based approaches for solving hierarchical optimization problems, (Sharda, R.; Golden, B. L.; Wasil, E.; Balci, O.; Stewart, W., Impacts of Recent Computer Advances on Operations Research (1989), North-Holland: North-Holland New York), 289-301
[2] Bard, J. F., Practical Bilevel Optimization. Algorithms and Applications (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 0943.90078
[3] Bialas, W. F.; Karwan, M. H., On two-level optimization, IEEE Transactions on Automatic Control, 27, 211-214 (1982) · Zbl 0487.90005
[4] Bialas, W. F.; Karwan, M. H., Two-level linear programming, Management Science, 30, 1004-1024 (1984) · Zbl 0559.90053
[5] Calvete, H. I.; Galé, C., On the quasiconcave bilevel programming problem, Journal of Optimization Theory and Applications, 98, 3, 613-622 (1998) · Zbl 0913.90240
[6] Dempe, S., Foundations of Bilevel Programming (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 1038.90097
[7] Dempe, S., Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52, 333-359 (2003) · Zbl 1140.90493
[8] Gendreau, M.; Marcotte, P.; Savard, G., A hybrid tabu-ascent algorithm for the linear bilevel programming problem, Journal of Global Optimization, 9, 1-14 (1996) · Zbl 0859.90097
[9] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[10] Goldberg, D. E., The Design of Innovation: Lessons from and for Competent Genetic Algorithms (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 1047.68162
[11] Hejazi, S. R.; Memariani, A.; Jahanshahloo, G.; Sepehri, M. M., Linear bilevel programming solution by genetic algorithm, Computers and Operations Research, 29, 1913-1925 (2002) · Zbl 1259.90120
[12] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI
[13] Mathieu, R.; Pittard, L.; Anandalingam, G., Genetic algorithms based approach to bi-level linear programming, RAIRO-Operations Research, 28, 1, 1-22 (1994) · Zbl 0857.90083
[14] Michalewick, Z., Genetic Algorithms+Data Structures=Evolution Programs (1996), Springer: Springer Berlin
[15] Nishizaki, I.; Sakawa, M.; Niwa, K.; Kitaguchi, Y., A computational method using genetic algorithms for obtaining Stackelberg solutions to two-level linear programming problems, Electronics and Communications in Japan, Part 3, 85, 6, 55-62 (2002)
[16] Rajesh, J.; Gupta, K.; Kusumakar, H. S.; Jayaraman, V. K.; Kulkarni, B. D., A tabu search based approach for solving a class of bilevel programming problems in chemical engineering, Journal of Heuristics, 9, 307-319 (2003)
[17] Reeves, C. R., Genetic algorithms for the operations researcher, INFORMS Journal on Computing, 9, 3, 231-250 (1997) · Zbl 0893.90145
[18] Sakin, K. H.; Ciric, A. R., A dual temperature simulated annealing approach for solving bilevel programming problems, Computers and Chemical Engineering, 23, 11-25 (1998)
[19] Wen, U. P.; Huang, A. D., A simple tabu search method to solve the mixed-integer linear bilevel programming problem, European Journal of Operational Research, 88, 3, 563-571 (1996) · Zbl 0908.90194
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.