Comparing Heuristics for Solving Linear Bilevel Problems

Bachelor Thesis, 2013

63 Pages, Grade: 1,0


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.

Table of Contents
Table of Content
List of Figures
List of
List of Symbo
2.1.1 General
2.1.2 A Bilevel Decentralized Capacitated Facility
8 Basic
1 Evaluation Metrics and Candidate
List S
0 Basic

iv Inhomogeneous and Homogeneous Modification
Development and Implementation of
4 Actualization of the Tabu List and

List of Figures
Figure 1: Structure of an iterative heuristic method
Figure 2: Tabu Search structure
...3 5
Figure 3: Actualization of the tabu list

List of Tables
Table 1: Comparison of different problem instances
solved with Tabu Search variant TS-T1
Table 2: Comparison of different Tabu Search variants
for solving instance i300_2
Table 3: Comparison of different candidate list and
intensification strateg
Table 4: Comparison of different problem instances
solved with Simulated Annealing variant SA-A-3
Table 5: Comparison of different Simulated Annealing variants
for solving instance i300_2

List of Symbols
General Mathematical Symbols:
Spaces, Matrices and Numbers:
the natural numbers
the real numbers
the n-dimensional real vector space
a matrix with line index and column index
limit approaching 0 from above or below
Sets and Set Operators:
set contains the elements
set is a subset of set
set is a proper subset of set
set is a superset of set
set is a proper superset of set
is an element of set
set contains the element
set is an empty set
set-theoretic difference
set-theoretic union
set-theoretic intersection
cardinality of set
closed interval from to
open interval from to

Relational Operators, Quantifiers and Arithmetic Operators:
definition signs
identical equality sign
relational operators: less, less or equal, much less
relational operators: greater, greater or equal, much greater
universal quantifier
existential quantifier
vertical bar for set properties
not further specified composition
difference operator
summation operator
a function mapping
natural exponential function
natural logarithm function
maximum or minimum of a set
argument of the maximum or minimum of a function
limit of a function
as approaches
derivative of
with respect to
Stochastic Symbols:
probability that takes the value
indicator function
continuous uniform distribution in the interval

Globally used Problem-specific Variables and Parameters:
Linear Programming:
minimization of the objective function
subject to all constraints contained in the vector
Problem-specific Sets:
set of potential plants
set of product types
subset of products that can be produced on plant ;
subset of plants that are able to produce product ;
Problem-specific Parameters:
opportunity cost per unit of unused production capacity if
plant is opened
demand of product
capacity consumption per unit for the production of product
in plant
production cost per capacity unit in plant
production capacity in plant
transportation cost of product produced in plant
setup cost for plant
large positive number

Problem-specific Decision Variables:
fraction of demand of product produced in plant
additional decision variables for the transformed model
Other Frequently Used Parameters:
solution space
set of moves
current solution
neighborhood function of a solution
general symbol for proximate solution from
selected proximate solution from
tabu list
tally parameter for Homogeneous Simulated Annealing
move value of the move leading from to
molar gas constant
Boltzmann constant

1 Introduction
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.
In this thesis, however, this usual facility location model, which can relatively
easily be solved as a linear optimization problem, becomes 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
The problem just described is a combinatorial one. Therefore, it is for larger
instances either not possible to perform a brute-force search that examines every
single candidate solution, because it is always an NP-hard problem due to its
exponential complexity (Audet et al., 1997). If there are positions to be
occupied by one of alternatives there are
possibilities to do this. In this case
, because the decision whether to open a facility or not is a binary one. This
leads to
possible solutions, if is the number of potential facilities in big O
. For example, if 100 facilities are considered, there are
possibilities how to solve this problem. For
instances that are still larger, this number increases accordingly in an exponential
Of course,
not all of these solutions come into consideration as potentially best solutions, as
some are infeasible (e.g. the null vector, i.e. choosing not a single plant which will
not satisfy the demand constraint) and others are not meaningful (e.g. selecting all
plants, which will produce enormous costs).
In view of these obstacles, other ways of solving such an optimization problem
have to be considered. For the bilevel facility location problem a combination of
heuristic search and linear programming suggests itself, because the subordinate

problem can be solved as a linear program with adequate software, whereas this is
not possible for the problem as a whole. Thus, the subordinate problem can be
embedded into a heuristic superstructure that optimizes the superordinate
objective function taking account of the sublevel problem. The applied heuristics
can be derived from different metaheuristics such as Tabu Search, Simulated
Annealing, Evolutionary Algorithms, Ant Colony Algorithms or Neural
Networks. As these methods are heuristic they cannot guarantee the global
optimality of the solution, but they can nevertheless generate good results
Within the scope of this thesis, existing literature on this topic is reflected first.
The problem on hand is described and two metaheuristic methods (Tabu Search
and Simulated Annealing) are introduced. One reason for comparing just these
two metaheuristics is the fact that one of them is deterministic and one
randomized, which enables statements on the meaningfulness of randomization.
Finally, different variants of applying these metaheuristics on the decentralized
capacitated facility location problem are worked out. The resulting algorithms
have been implemented with Xpress IVE. Test data have been used to evaluate
and compare the different approaches.

2 Review on Literature and Research
This chapter should give an overview of the theoretical foundations of bilevel
programming as well as metaheuristic methods. In particular, the two
metaheuristics that have been implemented within the scope of this thesis are
explained in detail.
2.1 Literature on Bilevel Programming
In this section general aspects of multilevel problems are introduced. Moreover,
the decentralized capacitated facility location problem is further described and
formulated as a linear programming model.
2.1.1 General Definition of Bilevel Programs
Linear optimization problems can be classified by the number of objective
functions, each of them nested in the superordinate ones. The case which is by far
most simple is a problem with only one objective function, a so-called monolithic
problem. Monolithic linear optimization problems are solvable with common
software using for example the Simplex method.
Multilevel problems, however, possess more than one objective function and are
much more difficult to be solved than monolithic ones. Let
be a set of objective functions. Let
further be
the set of all solutions of this program
a constraints vector. can be partitioned into subsets with the
following relation:

A multilevel problem can thus be described as an entity of hierarchically nested
programming problems
(Bialas, Karwan, 1978):
Bilevel problems are a special case of such hierarchical multilevel problems with
two objective functions (
). They consist of an outer and an inner problem,
whereupon the inner one contains the constraints as can be seen in the foregoing
Solving multilevel problems and hence also bilevel ones is by no means trivial. As
an optimality-guaranteeing approach is rather difficult, heuristic methods are
applied. In order to make a statement regarding the performance of different
heuristics, several methods have to be compared.
2.1.2 A Bilevel Decentralized Capacitated Facility Location Problem
As the facility location problem is regarded in a decentralized environment it is
not easily possible to represent this problem by a monolithic model (Cao, Chen,
2004). Instead, the decision-making process consists of two hierarchical levels.
On the upper level the so-called
, which means that the
plants to be opened are selected centrally. The second level decision the
however, has been delegated over all selected plants. As this sublevel decision
also affects the upper level due to its consequences on the arising cost, the
relationship between the two levels is a reciprocal one. Therefore, the problem on
hand can also be seen in a game-theoretical context with a leader and a follower.
Cao and Chen (2004) have formulated the following bilevel optimization model
out of this problem, whereupon a redundant constraint has been discarded here:
Excerpt out of 63 pages


Comparing Heuristics for Solving Linear Bilevel Problems
Technical University of Munich  (Lehrstuhl für Betriebswirtschaftslehre – Logistik und Supply Chain Management)
Catalog Number
ISBN (eBook)
ISBN (Book)
File size
2108 KB
metaheuristics, bilevel programming, linear programming, optimization, Tabu Search, Simulated Annealing, facility location
Quote paper
Florian Grodeke (Author), 2013, Comparing Heuristics for Solving Linear Bilevel Problems, Munich, GRIN Verlag,


  • No comments yet.
Read the ebook
Title: Comparing Heuristics for Solving Linear Bilevel Problems

Upload papers

Your term paper / thesis:

- Publication as eBook and book
- High royalties for the sales
- Completely free - with ISBN
- It only takes five minutes
- Every paper finds readers

Publish now - it's free