Comparing Heuristics for Solving Linear Bilevel Problems

Table of Contents

1 Introduction

2 Review on Literature and Research

2.1 Literature on Bilevel Programming

2.1.1 General Definition of Bilevel Programs

2.1.2 A Bilevel Decentralized Capacitated Facility Location Problem

2.2 Literature on Metaheuristics

2.2.1 Tabu Search

2.2.1.1 Basic Principles

2.2.1.2 Neighborhood Creation and Evaluation

2.2.1.3 Tabu List and Tabu Tenure

2.2.1.4 Aspiration Criteria

2.2.1.5 Evaluation Metrics and Candidate List Strategies

2.2.1.6 Intensification and Diversification Strategies

2.2.1.7 Further Aspects of Tabu Search

2.2.2 Simulated Annealing

2.2.2.1 Basic Principles

2.2.2.2 Mathematical and Thermodynamical Background

2.2.2.3 Inhomogeneous and Homogeneous Simulated Annealing

2.2.2.4 Cooling Schemes

2.2.2.5 Modifications of the Standard Procedure

3 Development and Implementation of Appropriate Heuristics

3.1 General Topics

3.1.1 Initial Solutions

3.1.2 Stop Criteria

3.1.3 Neighborhood Generation

3.2 Tabu Search

3.2.1 Implementation of a Tabu List

3.2.1.1 Actualization of the Tabu List and Tabu Tenure Arrays

3.2.1.2 Evaluation of the Neighborhood

3.2.2 Implemented Tabu Search Variants

3.3 Simulated Annealing

3.3.1 Variation of the Neighborhood Function

3.3.2 Implemented Simulated Annealing Variants

4 Numerical Studies

5 Conclusions and Outlook

Research Objectives and Key Topics

The primary objective of this thesis is to deduce, implement, and assess metaheuristic solution approaches for the decentralized capacitated facility location problem. As this problem is characterized as a combinatorial bilevel problem with NP-hard complexity, it cannot be solved efficiently through standard linear programming. The study aims to evaluate the effectiveness of Tabu Search and Simulated Annealing in finding optimal or near-optimal solutions by testing various algorithm configurations.

• Metaheuristic comparison between Tabu Search and Simulated Annealing.
• Transformation of bilevel problems into mixed-integer linear programming models.
• Implementation and parameterization of Tabu Search variants (static vs. dynamic tenures, candidate list strategies).
• Analysis of Simulated Annealing cooling schemes and neighborhood function variations.
• Empirical evaluation of algorithm performance based on varied problem instance sizes.

Extract from the Book

Chapter Summary

1 Introduction: Provides an overview of the facility location problem, explaining its bilevel nature and the necessity of using metaheuristics due to NP-hard complexity.

2 Review on Literature and Research: Discusses the theoretical background of bilevel programming and introduces the core concepts of Tabu Search and Simulated Annealing.

3 Development and Implementation of Appropriate Heuristics: Details the practical implementation of the metaheuristic algorithms, including initial solution generation, stop criteria, and neighborhood transformation.

4 Numerical Studies: Presents the experimental results of the algorithms tested on 60 data sets of varying sizes and discusses the impact of parameter settings.

5 Conclusions and Outlook: Summarizes findings, noting that Tabu Search generally outperformed Simulated Annealing, and suggests avenues for future research such as implementing more sophisticated influence measures.

Keywords

Bilevel programming, Facility location problem, Metaheuristics, Tabu Search, Simulated Annealing, Combinatorial optimization, NP-hard, Local optimum, Neighborhood function, Tabu tenure, Cooling schedule, Intensification, Diversification, Linear programming, Algorithm performance.

Frequently Asked Questions

What is the core focus of this academic work?

This thesis focuses on comparing different metaheuristic methods to solve the decentralized capacitated facility location problem, which is structured as a complex combinatorial bilevel optimization problem.

What are the primary algorithmic approaches compared in the research?

The research primarily evaluates and compares the performance of Tabu Search and Simulated Annealing as metaheuristic techniques for navigating the solution space.

What is the main objective of the thesis?

The main objective is to determine which metaheuristic algorithms and parameter settings yield the best solutions for a hierarchical facility location model that cannot be solved through simple linear programming.

Which scientific methodology is employed to solve the problem?

The author employs a combination of heuristic search and linear programming, where the subordinate facility location problem is solved as a linear program embedded within the metaheuristic superstructure.

What is discussed in the main body of the work?

The main body covers the theoretical foundations of bilevel programming, detailed explanations of Tabu Search and Simulated Annealing principles, and the development and testing of specific algorithm variants using Xpress IVE.

Which terms best characterize this research?

Key terms include bilevel programming, combinatorial optimization, metaheuristics, facility location, and performance analysis of search algorithms.

Why is the "decentralized" nature of the facility location problem significant?

The decentralized nature means the decision-making process is divided into two hierarchical levels—the principal firm (leader) and the plants (followers)—which creates reciprocal constraints that preclude simple monolithic linear optimization.

How does Tabu Search differ from Simulated Annealing in this study?

Tabu Search is characterized as a deterministic approach utilizing memory (tabu lists) to avoid cycling, while Simulated Annealing is a randomized approach that uses a temperature-based cooling scheme to escape local optima.

What do the numerical results reveal about algorithm performance?

The results indicate that while some Tabu Search variants can find the global optimum reliably, Simulated Annealing performed worse, often struggling with "swinging" effects between solutions at low temperatures.