European Journal of Operational Research 257 (2017) 395–411
Contents lists available at ScienceDirect
European Journal of Operational Research
journal homepage: www.elsevier.com/locate/ejor
Continuous Optimization
Evolutionary algorithm for bilevel optimization using approximations
of the lower level optimal solution mapping
Ankur Sinha
a , ∗
, Pekka Malo
b
, Kalyanmoy Deb
c
a
Production and Quantitative Methods, Indian Institute of Management Ahmedabad Vastrapur, Ahmedabad 380015, India
b
Department of Information and Service Economy, Aalto University School of Business, PO Box 21220, 0 0 076 Aalto, Helsinki, Finland
c
Department of Electrical and Computer Engineering, Michigan State University, East Lansing 48823, MI, USA
a r t i c l e i n f o
Article history:
Received 24 April 2015
Accepted 10 August 2016
Available online 17 August 2016
Keywords:
Bilevel optimization
Evolutionary algorithms
Quadratic approximations
a b s t r a c t
Bilevel optimization problems are a class of challenging optimization problems, which contain two levels
of optimization tasks. In these problems, the optimal solutions to the lower level problem become possi-
ble feasible candidates to the upper level problem. Such a requirement makes the optimization problem
difficult to solve, and has kept the researchers busy towards devising methodologies, which can efficiently
handle the problem. Despite the effort s, there hardly exist s any effective methodology, which is capable
of handling a complex bilevel problem. In this paper, we introduce bilevel evolutionary algorithm based
on quadratic approximations (BLEAQ) of optimal lower level variables with respect to the upper level
variables. The approach is capable of handling bilevel problems with different kinds of complexities in
relatively smaller number of function evaluations. Ideas from classical optimization have been hybridized
with evolutionary methods to generate an efficient optimization algorithm for a wide class of bilevel
problems. The performance of the algorithm has been evaluated on two sets of test problems. The first
set is a recently proposed SMD test set, which contains problems with controllable complexities, and the
second set contains standard test problems collected from the literature. The proposed method has been
compared against three benchmarks, and the performance gain is observed to be significant. The codes
related to the paper may be accessed from the website http://bilevel.org .
© 2016 Elsevier B.V. All rights reserved.
1. Introduction
Bilevel optimization is a branch of optimization, which con-
tains a nested optimization problem within the constraints of the
outer optimization problem. The outer optimization task is usually
referred to as the upper level optimization problem, and the in-
ner optimization task is referred to as the lower level optimiza-
tion problem. The lower level problem appears as a constraint,
such that only an optimal solution to the lower level optimization
problem is a possible feasible candidate to the upper level opti-
mization problem. Such a requirement makes bilevel optimization
problems difficult to handle and have kept researchers and prac-
titioners busy alike. The hierarchical optimization structure may
introduce difficulties such as non-convexity and disconnectedness
even for simpler instances of bilevel optimization like bilevel lin-
ear programing problems. Bilevel linear programing is known to
be strongly NP-hard ( Hansen, Jaumard, & Savard, 1992 ), and it has
∗
Corresponding author.
E-mail addresses: asinha@iima.ac.in , ankur.sinha@gmail.com (A. Sinha), pekka.
malo@aalto.fi (P. Malo), kdeb@egr.msu.edu (K. Deb).
been proven that merely evaluating a solution for optimality is also
a NP-hard task ( Vicente, Savard, & Judice, 1994 ). This gives us an
idea about the kind of challenges offered by bilevel problems with
complex (non-linear, non-convex, discontinuous etc.) objective and
constraint functions.
In the field of classical optimization, a number of studies have
been conducted on bilevel programing ( Colson, Marcotte, & Savard,
2007; Dempe, Dutta, & Lohse, 2006; Vicente & Calamai, 2004 ). So-
lution techniques commonly employed to handle bilevel problems
often require simplifying assumptions like smoothness, linearity or
convexity. Some of the classical approaches used to handle bilevel
problems include the Karush–Kuhn–Tucker approach ( Bialas &
Karwan, 1984; Bianco, Caramia, & Giordani, 2009; Chen & Florian,
1992; Herskovits, Leontiev, Dias, & Santos, 20 0 0 ), Branch-and-
bound techniques ( Bard & Falk, 1982; Fortuny-Amat & McCarl,
1981 ), and the use of penalty functions ( Aiyoshi & Shimizu, 1981 ).
Most of these solution methodologies are rendered inapplicable,
as soon as the bilevel optimization problem becomes complex.
Heuristic procedures such as evolutionary algorithms have also
been developed for handling bilevel problems with higher levels
of complexity ( Wang, Wan, Wang, & Lv, 20 08; Yin, 20 0 0 ). Most
of the existing evolutionary procedures often involve enormous
http://dx.doi.org/10.1016/j.ejor.2016.08.027
0377-2217/© 2016 Elsevier B.V. All rights reserved.
- 1
- 2
- 3
前往页