IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v166y2009i1p39-5610.1007-s10479-008-0416-0.html
   My bibliography  Save this article

A genetic algorithm for solving linear fractional bilevel problems

Author

Listed:
  • Herminia Calvete
  • Carmen Galé
  • Pedro Mateo

Abstract

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. In this paper a genetic algorithm is proposed for the class of bilevel problems in which both level objective functions are linear fractional and the common constraint region is a bounded polyhedron. The algorithm associates chromosomes with extreme points of the polyhedron and searches for a feasible solution close to the optimal solution by proposing efficient crossover and mutation procedures. The computational study shows a good performance of the algorithm, both in terms of solution quality and computational time. Copyright Springer Science+Business Media, LLC 2009

Suggested Citation

  • Herminia Calvete & Carmen Galé & Pedro Mateo, 2009. "A genetic algorithm for solving linear fractional bilevel problems," Annals of Operations Research, Springer, vol. 166(1), pages 39-56, February.
    • Handle: RePEc:spr:annopr:v:166:y:2009:i:1:p:39-56:10.1007/s10479-008-0416-0
    DOI: 10.1007/s10479-008-0416-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-008-0416-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-008-0416-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Calvete, Herminia I. & Gale, Carmen & Mateo, Pedro M., 2008. "A new approach for solving linear bilevel problems using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 188(1), pages 14-28, July.
    2. Colin R. Reeves, 1997. "Feature Article---Genetic Algorithms for the Operations Researcher," INFORMS Journal on Computing, INFORMS, vol. 9(3), pages 231-250, August.
    3. H. I. Calvete & C. Galé, 1998. "On the Quasiconcave Bilevel Programming Problem," Journal of Optimization Theory and Applications, Springer, vol. 98(3), pages 613-622, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hecheng Li, 2015. "A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems," Annals of Operations Research, Springer, vol. 235(1), pages 543-558, December.
    2. Ashenafi Woldemariam & Semu Kassa, 2015. "Systematic evolutionary algorithm for general multilevel Stackelberg problems with bounded decision variables (SEAMSP)," Annals of Operations Research, Springer, vol. 229(1), pages 771-790, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hecheng Li, 2015. "A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems," Annals of Operations Research, Springer, vol. 235(1), pages 543-558, December.
    2. Lei Fang & Hecheng Li, 2013. "Lower bound of cost efficiency measure in DEA with incomplete price information," Journal of Productivity Analysis, Springer, vol. 40(2), pages 219-226, October.
    3. Zhou, Shengchao & Xie, Jianhui & Du, Ni & Pang, Yan, 2018. "A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capacities and arbitrary job sizes," Applied Mathematics and Computation, Elsevier, vol. 334(C), pages 254-268.
    4. Martha-Selene Casas-Ramírez & José-Fernando Camacho-Vallejo & Juan A. Díaz & Dolores E. Luna, 2020. "A bi-level maximal covering location problem," Operational Research, Springer, vol. 20(2), pages 827-855, June.
    5. Hui-Chin Tang & Chiang Kao, 2004. "Searching for Good Multiple Recursive Random Number Generators via a Genetic Algorithm," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 284-290, August.
    6. René Y. Glogg & Anna Timonina-Farkas & Ralf W. Seifert, 2022. "Modeling and mitigating supply chain disruptions as a bilevel network flow problem," Computational Management Science, Springer, vol. 19(3), pages 395-423, July.
    7. Sinha, Ankur & Malo, Pekka & Deb, Kalyanmoy, 2017. "Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping," European Journal of Operational Research, Elsevier, vol. 257(2), pages 395-411.
    8. Ya Gao & Guangquan Zhang & Jie Lu & Hui-Ming Wee, 2011. "Particle swarm optimization for bi-level pricing problems in supply chains," Journal of Global Optimization, Springer, vol. 51(2), pages 245-254, October.
    9. Calvete, Herminia I. & Galé, Carmen, 2011. "On linear bilevel problems with multiple objectives at the lower level," Omega, Elsevier, vol. 39(1), pages 33-40, January.
    10. Tadashi Yamada & Bona Frazila Russ & Jun Castro & Eiichi Taniguchi, 2009. "Designing Multimodal Freight Transport Networks: A Heuristic Approach and Applications," Transportation Science, INFORMS, vol. 43(2), pages 129-143, May.
    11. Nils Boysen & Dirk Briskorn & Simon Emde, 2018. "Scheduling electric vehicles and locating charging stations on a path," Journal of Scheduling, Springer, vol. 21(1), pages 111-126, February.
    12. Chia-Shin Chung & James Flynn & Walter Rom & Piotr Staliński, 2012. "A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems," Journal of Entrepreneurship, Management and Innovation, Fundacja Upowszechniająca Wiedzę i Naukę "Cognitione", vol. 8(2), pages 26-43.
    13. Menasri, R. & Nakib, A. & Daachi, B. & Oulhadj, H. & Siarry, P., 2015. "A trajectory planning of redundant manipulators based on bilevel optimization," Applied Mathematics and Computation, Elsevier, vol. 250(C), pages 934-947.
    14. Xiao, Helu & Ren, Tiantian & Zhou, Zhongbao & Liu, Wenbin, 2021. "Parameter uncertainty in estimation of portfolio efficiency: Evidence from an interval diversification-consistent DEA approach," Omega, Elsevier, vol. 103(C).
    15. Xueping Zhu & Chi Zhang & Guangtao Fu & Yu Li & Wei Ding, 2017. "Bi-Level Optimization for Determining Operating Strategies for Inter-Basin Water Transfer-Supply Reservoirs," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 31(14), pages 4415-4432, November.
    16. R. Paulavičius & C. S. Adjiman, 2020. "New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm," Journal of Global Optimization, Springer, vol. 77(2), pages 197-225, June.
    17. Jianyuan Zhai & Fani Boukouvala, 2022. "Data-driven spatial branch-and-bound algorithms for box-constrained simulation-based optimization," Journal of Global Optimization, Springer, vol. 82(1), pages 21-50, January.
    18. Satyajith Amaran & Nikolaos V. Sahinidis & Bikram Sharda & Scott J. Bury, 2016. "Simulation optimization: a review of algorithms and applications," Annals of Operations Research, Springer, vol. 240(1), pages 351-380, May.
    19. Dimitris Fouskakis & David Draper, 2002. "Stochastic Optimization: a Review," International Statistical Review, International Statistical Institute, vol. 70(3), pages 315-349, December.
    20. Fernando Tavares-Pereira & José Figueira & Vincent Mousseau & Bernard Roy, 2007. "Multiple criteria districting problems," Annals of Operations Research, Springer, vol. 154(1), pages 69-92, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:166:y:2009:i:1:p:39-56:10.1007/s10479-008-0416-0. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.