Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Business economics - Operations Research

Comparing Heuristics for Solving Linear Bilevel Problems

Title: Comparing Heuristics for Solving Linear Bilevel Problems

Bachelor Thesis , 2013 , 63 Pages , Grade: 1,0

Autor:in: Florian Grodeke (Author)

Business economics - Operations Research
Excerpt & Details   Look inside the ebook
Summary Excerpt Details

In this thesis, metaheuristic solution approaches for the decentralized capacitated facility location problem are deduced, implemented and assessed. As the mentioned problem is a combinatorial bilevel problem it is not easily solvable by means of linear programming. Therefore, different metaheuristic techniques, namely Tabu Search and Simulated Annealing, are used. Each of them is split into several variants. Tabu Search has turned out to deliver better results than Simulated Annealing and converges also from bad initial solutions towards the global optimum. However, the performance of the algorithms is highly dependent on the concrete parameter settings. Thus, the gap between the optimum found and the global optimum can vary from 0 to a multiple of the global optimum depending on the used variant.

The thesis on hand describes the comparison of different metaheuristics in order to generate solutions for the bilevel decentralized capacitated facility location problem. This optimization problem consists of choosing a set of facilities to be opened out of a superset of potential facilities. The objective is to minimize cost, while taking certain constraints into account.

This usual facility location model, which can relatively easily be solved as a linear optimization problem, will be expanded. There is an additional submodel that is intended to develop an optimal production plan for the facilities chosen within the superordinate model. On the sublevel, also cost has to be minimized and as one major constraint the entire external demand has to be satisfied. Such a bilevel problem containing two hierarchically arranged objective functions cannot be solved using the usual methods of linear programming any more.

Excerpt


Inhaltsverzeichnis (Table of Contents)

  • Introduction
  • Review on Literature and Research
    • Literature on Bilevel Programming
      • General Definition of Bilevel Programs
      • A Bilevel Decentralized Capacitated Facility Location Problem
    • Literature on Metaheuristics
      • Tabu Search
        • Basic Principles
        • Neighborhood Creation and Evaluation
        • Tabu List and Tabu Tenure
        • Aspiration Criteria
        • Evaluation Metrics and Candidate List Strategies
        • Intensification and Diversification Strategies
        • Further Aspects of Tabu Search
      • Simulated Annealing
        • Basic Principles
        • Mathematical and Thermodynamical Background
        • Inhomogeneous and Homogeneous Simulated Annealing
        • Cooling Schemes
        • Modifications of the Standard Procedure
  • Development and Implementation of Appropriate Heuristics
    • General Topics
      • Initial Solutions
      • Stop Criteria
      • Neighborhood Generation
    • Tabu Search
      • Implementation of a Tabu List
        • Actualization of the Tabu List and Tabu Tenure Arrays
        • Evaluation of the Neighborhood
      • Implemented Tabu Search Variants
    • Simulated Annealing
      • Variation of the Neighborhood Function
      • Implemented Simulated Annealing Variants
  • Numerical Studies

Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)

This thesis explores metaheuristic solution approaches for the decentralized capacitated facility location problem, a complex combinatorial bilevel problem not easily solved by linear programming. The primary objective is to develop, implement, and assess the effectiveness of different metaheuristic techniques, specifically Tabu Search and Simulated Annealing, in finding optimal solutions.

  • Bilevel programming and its application to the decentralized capacitated facility location problem
  • Metaheuristic approaches for solving complex optimization problems
  • Implementation and comparison of Tabu Search and Simulated Annealing algorithms
  • Assessment of algorithm performance and parameter sensitivity
  • Evaluation of the effectiveness of different algorithm variants

Zusammenfassung der Kapitel (Chapter Summaries)

The first chapter provides an introduction to the research topic, outlining the problem of decentralized capacitated facility location and its relevance in the context of bilevel programming. Chapter two presents a comprehensive review of relevant literature, covering both bilevel programming and metaheuristic techniques, particularly Tabu Search and Simulated Annealing. The chapter delves into the theoretical foundations and practical considerations of each technique, highlighting key concepts and methodologies. Chapter three focuses on the development and implementation of appropriate heuristics. It discusses general topics such as initial solutions, stop criteria, and neighborhood generation, followed by detailed explanations of the implementation of Tabu Search and Simulated Annealing variants. Chapter four presents numerical studies, analyzing the performance of the developed algorithms on various test instances. The results are discussed and compared, evaluating the effectiveness and limitations of each approach.

Schlüsselwörter (Keywords)

This work focuses on the intersection of bilevel programming, metaheuristic optimization, and the decentralized capacitated facility location problem. Key terms include: bilevel programming, metaheuristics, Tabu Search, Simulated Annealing, decentralized capacitated facility location, combinatorial optimization, algorithm performance, parameter sensitivity, and solution quality.

Excerpt out of 63 pages  - scroll top

Details

Title
Comparing Heuristics for Solving Linear Bilevel Problems
College
Technical University of Munich  (Lehrstuhl für Betriebswirtschaftslehre – Logistik und Supply Chain Management)
Grade
1,0
Author
Florian Grodeke (Author)
Publication Year
2013
Pages
63
Catalog Number
V336709
ISBN (eBook)
9783668266322
ISBN (Book)
9783668266339
Language
English
Tags
metaheuristics bilevel programming linear programming optimization Tabu Search Simulated Annealing facility location
Product Safety
GRIN Publishing GmbH
Quote paper
Florian Grodeke (Author), 2013, Comparing Heuristics for Solving Linear Bilevel Problems, Munich, GRIN Verlag, https://www.grin.com/document/336709
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • https://cdn.openpublishing.com/images/brand/1/preview_popup_advertising.jpg
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  63  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint