DSf

5 June 2017

OutlineEvolutionary Bilevel Optimization:
Applications and Methods

Ankur Sinha

Kalyanmoy Deb

Production and Quantitative Methods

Electrical and Computer Engineering

Indian Institute of Management
Ahmedabad, India
asinha@iimahd.ernet.in

Michigan State University
East Lansing, MI 48864, USA
kdeb@egr.msu.edu

Source: http://www.bilevel.org

ØBilevel Optimization: An IntroductionØGenesisØ

Efficient Solution Methodologies

Ø

Test Problem ConstructionØ

ResultsØ

Multi-objective Bilevel Optimization

ØApplications

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

What is Bilevel Optimization?

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

An Illustrationo Lower level solution xl can be a singleton or multi-valuedo Upper level solution corresponds to the best combination of lower
level optimum and upper level values

Two levels of optimization tasks
Upper level: (xu,xl)o Uncertainty about which point the lower level decision maker chooses
makes the bilevel formulation ill-defined

Lower level: (xl), xu is fixed

An upper level feasible solution must be an optimal lower
level solution: (xu, xl*(xu))
Min is default, can be
max in any of the levels

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Single
LL solution

Multiple
LL solutions

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

1

DSf

5 June 2017

Origin of Bilevel Programming

Multi-level Optimization•

Multi-level (L levels) optimization• Two or more levels of optimization•

Nested structure
Min F(x1,x2,…xL)
s.t

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

No of Articles

HistoryTime

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

2

DSf

5 June 2017

Topic Models

Topic Models

More than 10% share

Around 5-10% share
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Topic Models

Topic Models

Around 5% shareLess than 5% share
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

3

DSf

5 June 2017

A Mathematical Bilevel Optimization
Problem
xu=x, xl=y
For a x,maximize y
Bold line issolution set for
LL
Min 3y+x forbold line issolution (6,2)

Not to be Confused with MultiObjective Optimization=xly’

Min x+3y, s.t. y≥y’ & feasible -> (x,y)*=(1,y’)xuSingle-obj optimum, if LL is absent

PO set very different from the Bilevel solution

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Single and Bi-objective Treatments

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Multi-level Optimization: A Generic
Optimization Problem
oMulti-level (L levels) optimizationoDoes not help solve Bilevel problem bynIgnoring of lower level ornTreating as a bi-objective optimization

oNeed to look at differently

n Two (L=2) or more levels of optimizationn Ideally, nested optimization

oUsual single, multi- and many-objective
optimization problems
n Special cases (L=1) of L-level optimizationn Number of objectives can be more than one at eachlevel

oBilevel: A more generic optimization
concept than single-level optimization
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

4

DSf

5 June 2017

Similarities with ConstrainedSingle-Objective Optimization with
Equality ConstraintsoA single-objective
optimization problem:

Some ApplicationsoEquality constraint:n Usually, a root-finding problem
n A solution x is feasible, only if it satisfies all constraintso In EBO, LL problem is an optimization problem
n A solution (xu,xl) is not feasible, unless xl is a solution to the LL
optimization problem
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Bilevel Problems in PracticeOften appears from functional feasibility
Stability, equilibrium, solution to a set of PDEs

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Structural OptimizationoUpper level: Topology
oLower level: Sizes and coordinates

Ideally, lower level task must implement above
Dual problem solving in theoretical optimization

Lower level is bypassed by approximation or by using
direct simplified solution principles
Due to lack of suitable BO techniques

Stackelberg games: Leader-follower
Leader must be restricted to follower’s decisions
Follower must respect leader’s decisions
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Does it make sense to know cross-section sizes
before settling down on topology?
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

5

DSf

5 June 2017Toll Setting Problem
Authority's (Upper level) problem:

o

l

l

o

Stackelberg Competition
Competition between a leader and afollower firm (Duopoly)

Authority responsible for highway systemwants to maximize its revenues earned fromtoll

Leader solves the following optimization
problem to maximize its profit

The authority has to solve the highway users
optimization problem for all possible tolls

Highway users' (Lower level) problem:ll

For any toll chosen by the authority, highway
users try to minimize their own travel costs

If the leader and follower have
similar functions, leader always
makes a higher profit.
- First mover’s advantage

A high toll will deter users to take thehighway, lowering the revenues

Does it make sense to choose or not
to choose a toll high-way before
knowing the toll amount?

Can be extended to multiple
leaders and multiple followers

Brotcorne et al. (2001)
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Taxation Strategy

Seller-Buyer
StrategiesnAn owner (UL) of a company dictates
the selling price and supply. She/hewants to maximize profit

Buyers (LL) look at the product quality,
pricing and various other options
available to maximize their utilityn Mixed integer programs on similar lines
have been formulated by Heliporn etal. (2010)
Does it make sense to buy a productand its utility without knowing the sale
Heilporn et al. (2010)
price?
n

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb• Recently, there had been acontroversy in Finland for gold
mining in the Kuusamo region Leader: Government Maximize
revenue from taxes, Minimize
in Finland
Pollution• The region is a famous tourist
resort endowed with immense
natural beauty• For any taxation strategy by
the government (UL), themining company (LL)
Follower: Mining Company
optimizes its own profits
Maximize Profit
Does it make sense for the miners toSinha, et al. (2013)venture into it before knowing thegovernmental tax policies?
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

6

DSf

5 June 2017

Defense Applications
Hub-and-Spoke Networks
Interdiction Problem

Protection Problem

Attacker-Defender

Defender-Attacker

Two levels

Two levels

Attacker
Maximize operating costs
post attack

DefenderMinimize the maximum
damage by fortification

DefenderMinimize operating cost

Attacker
Maximize damage

Robust Design
Defender-Attacker-Defender
Three levels
DefenderTake interdiction problem into
account during design phase
Attacker
Maximize operating costs
post attack

Upper Level
Regulator
Objective 1: Minimize Pollution (Fertilizer)
Objective 2: Maximize Revenues

Lower Level
Multiple Farms
Objective: Maximize Individual Profit

DefenderMinimize operating cost
Decision Variables: Taxation, inputs, outputs

Nine key substations out of 55,000 substations canresult in a coast to coast blackout in US
WSJ Link

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Parameter Tuning
Upper Level: Find optimal
parameters that maximize
algorithm performance overa number of initialconditions
Lower Level: Run the
optimization algorithm tofind optimized solution
Researchers commonly rely on
grid search or random search

Does it make sense to conclude an
Bennett et al. (2008), CEC-2017,
Sinha etal. (2014)
algorithm’s performance without
San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb
spelling out algorithm parameters?

sfdsFDSA

Agri-business Management

Does it make sense to decide on
fertilizer usage before knowing the tax
on it?

Contains multiple lower level
optimization problems

Whittaker
et al. (2016)
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Inverse Optimal Control• While performing actions humans
optimize certain unknown costfunction• It might be interesting to have an ideaof the cost function that might help indesigning efficient humanoids• Given the data corresponding to the
motion identifying the reward or costfunction becomes an inverse problem
Mombaur et al. (2010), Suryan et al. (2016)
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

7

DSf

5 June 2017

Solution Methodologies

Min-Max Problems• Single-level reduction using KKT- Bialas and Karwan (1984), Bard and Falk (1982), Bard
and Moore (1990)• Descent methods- Savard and Gauvin (1994), Vicente et al. (1994)• Penalty function methods- Aiyoshi and Shimizu (1981, 1984), Ishijuka and Aiyoshi(1992), White and Anandalingam (1993)• Trust region methods- Colson et al. (2005)• Using lower level optimal value function- Mitsos (2010)

o Typical min-max problem

o Can be solved as a Bilevel problem

o Co-evolutionary problems are ideal candidates for
Bilevel optimization

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Special Cases
l

l

l

l

Properties of Bilevel Problems

Linear bilevel problemsl Reducible to a mixed integer linear program
Bilevel problems with combinatorial variables at
upper level and linear program at lower levell Reducible to a mixed integer linear program
Bilevel problems with combinatorial variables at bothlevelsl Very hard to solve
Bilevel problems with similar objectives at both levelsl Reduces to minmax or minmin (min) problems
l Ideas of duality can be utilized
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSAl

Bilevel problems are typically non-convex,
disconnected and strongly NP-hardlSolving an optimization problem produces one ormore feasible solutionslMultiple global solutions at lower level can induce
additional challengesl

Two levels can be cooperating or conflicting
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

8

DSf

5 June 2017

Why Use Evolutionary Algorithms?
First, no implementable mathematical optimality conditions exist(Dempe, Dutta, Mordokhovich, 2007)•

LL problem is replaced with KKT conditions and constraint
qualification (CQ) conditions of LL•

UL problem requires KKT of LL-KKT conditions, but handling
LL-CQ conditions in UL-KKT becomes difficult
Involves second-order differentials•

Moreover, classical numerical optimization methods requirevarious simplifying assumptions like continuity, differentiability
and convexity•

Most real-world applications do not follow these assumptions

EA’s flexible operators, direct use of objectives, and population
approach should help solve BO problems better
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

EAs for Bilevel Optimization• Most of the EAs for bilevel optimization have been nested innature- Using one algorithm for upper level and solving thelower level optimization problem for every upper level
point- Not very interesting!
- Expensive even for small instances!
- Non-scalable!

Niche of Evolutionary Methods (cont.)
o Usually, LL solutions are multi-modalo Usually, BO problems are multi-objective BOn Both problems require to find and maintain multiple

Importantly,
classical or theoretical optimization
optimal solutions
literature
not provide
usfor
with
good
methods
n EAs aredo
known
to be goodthese
scenariosandapplicable
resultso Computationally faster methods possible through metamodeling etc.
o Other complexities (robustness, parallel implementation,
fixed budget) can be handled efficiently
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Bilevel Optimization using EAs
EA at upper level and exact method at lower level• Mathieu et al. (1994): LP for lower level and GA for upper level• Yin (2000): Frank-Wolfe Algorithm for lower level and EA for
upper level
EA at both upper and lower level• Li et al. (2006): Particle Swarm Optimization at both levels• Angelo et al. (2013): Differential Evolution at both levels• Sinha et al. (2014): Genetic Algorithm at both levels
EA used after single-level reduction• EA researchers have also tried replacing the lower level problems
using KKT (Hejazi et al. (2002), Wang et al. (2008), Li et al.
(2007))

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

9

DSf

5 June 2017

Bilevel Optimization using EAs

Can EAs be really useful for bilevel
optimization?

Approximating lower level level rational response• Sinha, Malo, Deb. (2013, 2014, 2017): Iteratively approximates
lower level optimal response with upper level decision vector(Discussed later)
Approximating lower level optimal value function• Sinha, Malo, Deb. (2016): Iteratively approximates lower level
optimal function value with upper level decision vector(Discussed later)

Trust region method• Sinha, Soun and Deb (2017)(To be presented on June 8, 14:30-16:30, Room 8)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Can EAs be really useful for bilevel
optimization?
• Nested approaches are certainly not the way forward

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Can EAs be really useful for bilevel
optimization?
• It is noteworthy that at each iteration an EA has apopulation of points• Can these population of points be put to use toapproximate certain mappings in bilevel?
• Exploiting the structure and properties of the
problem is essential!

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

10

DSf

5 June 2017

Better Understanding of Bilevel
Problems

Approach 1(Lower Level Reaction Set Mapping)f (x(2)u ,x l )F (x u , Ψ(x u))

Multiple
LL solutions

f (x*u , x l)
XUf (x(1)
u ,x l )
x(2)
u
x u*

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Mapped xl* = Ψ(xu)XL

F (x u , Ψ (x u ) )

x(1)
u

C

B
(1)
Ψ(x u ){

Step 0: Solve the lower level problem completely for the initial population
Step 1: Use the population members to approximate the Ψ-mapping locally
Step 2: Solve the reduced single level problem for a few iterations
Step 3: Update the local Ψ-mappings and continue
Step 4: If termination criteria not met, go to Step 2

Ψ(x u* ) ={x*l}(2)
Ψ(x u )

A

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

XLActual Ψ-mappingΨ-MappingF

Upper-level decision space
b
d

a

c

Mapped xl*

Ψ (x *u )

Ψ(b)

Ψ(d)

BilevelMinimumΨ(a)Ψ (x u )x (1)uLower-level decision space
x (2)
u

x *u

Upper-level variable vector

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Ψ(c)XU
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

11

DSf

5 June 2017

Approximate Ψ-mapping

Using approximate Ψ-mapping

Upper-level decision space

Upper-level decision space

b
d

a

b
d

c

Ψ(b)

Ψ(d)

a

c

Ψ(b)

Ψ(d)

Ψ(a)

Lower-level decision space

e

Ψ(a)
Ψ(c)

Ψ(c)

Lower-level decision space

For new upper level point ‘e’, we need not solve the lower level problem, as an approximate estimate is available
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Approximation Choice

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Set-valued Ψ becomes problematic
Upper-level decision space• Tried different strategies for localized approximation, like,• Linear Approximation• Piecewise linear approximation• Quadratic approximation• Results were favorable and similar with piecewise-linear aswell as quadratic approximation• Decided to use quadratic approximation because of its
simplicity• More complex techniques like neural networks are an
obvious extension but require large number of points

b
d

c

a

Ψ(b)
Ψ(d)
Ψ(a)

Lower-level decision spaceΨ(c)Dual challenge: 1. Finding the set and 2. Approximating the set
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

12

DSf

5 June 2017

Efficient Evolutionary Bilevel
Optimization Algorithm (BLEAQ)
oNested algorithm is expensiveoTrain a meta-model for xl*(xu)oQuadratic approximation of the inducible
regionnBLEAQ constructs Ψ (Sinha, Malo and Deb, 2013)

Meta-model of Ψ(xu)

BLEAQ is being
modified for handling
multiple LL solutions

XL
Meta-model

Approximation
Error

ψ (x u )(1)ψ (x u )(1)
Ψ(x u )(0)
Ψ(x u ) = ψ (x(0)u)

Mapped xl*

oUse meta-model until possible, else solve LL
optimization problemΨ (x u )CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

BLEAQ

Initialization

Upper-level variable vector X
U
x (0)
u

CEC-2017, San Sebastian, Spainx (1)uAnkur Sinha and Kalyanmoy Deb

Approach 2(Optimal Value Function Mapping)

Lower Level Optimization
Termination
Check

Produce Offspring

No

Stop

Yes

Quadratic Approximationof Ψ Function
Update Population

YesIs
Approximation
Good?

Accept Lower Level Variables
as Offspring

No
Lower Level Optimization for Offspring
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Step 0: Solve the lower level problem completely for the initial population
Step 1: Use the population members to approximate the φ-mapping locally
Step 2: Solve the reduced single level problem for a few iterations
Step 3: Update the local φ-mappings and continue
Step 4: If termination criteria not met, go to Step 2
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

13

DSf

5 June 2017

IssuesIssues+ εi• The approximate φ-mapping makes the region highly constrained• With errors in estimation of φ-mapping the reduced problem might become
infeasible• The approximate φ-mapping makes the region highly constrained• With errors in estimation of φ-mapping the reduced problem might become
infeasible• Therefore, we relax the φ-constraint using εi

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Debf (x(3)u ,x l )f ( xu , xl )ϕ (x u )XU

Comparison of Two Methodsf (x(2)u ,x l)XUf (x(1)
u ,x l )
x(3)
u

x(3)
u
x(2)
u
x(1)
u

Approaches to 0 withincrease in iterations i

x (2)
u
x(1)
u

Approach 1

Approach 2

To be solved only with respect to xu

To be solved with respect to xu and xl

C

Inset 3B

A

Inset 1XL

• φ being a function is easier
to approximate than Ψ

XU
x(3)
u

Inset 2
x(2)
u
(1)

xu

Ψ−Mapping(1)

Ψ(x u )(2)
Ψ(x u )(3)
Ψ(x u )XL

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

14

DSf

5 June 2017

Test Problems

Test Problems• Given that a convergence proof is difficult, we
can only use test problems to justify that theideas work!
• First, we begin with some simple test problems

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Test Problems

Test Problems

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

15

DSf

5 June 2017

Test Problems

Results on TPs

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Results on TPs (Cont.)

Sinha et al. (2016)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Comparison with other approaches
21 runs

Most of the evaluations were spent in initialization

WJL – Wang et al. (2005), WLD – Wang et al. (2011)
Sinha et al. (2016)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

16

DSf

5 June 2017

Let us modify the test problems!

Results (Modified Test Problems)
21 runs
Upper Level Function
Evaluations

Lower Level Function
Evaluations

Both Methods Fail

Modification leads to multiple lower level optimal
solutions for each upper level decision vector

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Bilevel Test Problem Construction

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Requirements• Controllable difficulty in convergence at upper and lower levels• Test problems with controllable difficulties are often
required to evaluate evolutionary algorithms• Controllable and segregated difficulties help toidentify that what aspects the algorithm is unable tohandle• Controllable difficulty caused by interaction of two levels• Multiple global solutions at the lower level for any given set of upper
level variables• Clear identification of relationships between lower level optimal
solutions and upper level variables• Scalability to any number of decision variables at upper and lower
levels• Constraints (preferably scalable) at upper and lower levels• Possibility to have conflict or cooperation at the two levels• The optimal solution of the bilevel optimization is known

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

17

DSf

5 June 2017

Bilevel Test Problems

Roles of Variables

Test Problem Framework

Table 1: Overview of test-problem framework components

The objectives and variables on both levels aredecomposed as follows:

Panel A: Decomposition of decision variables
Upper-level variables
Lower-level variables
VectorPurpose
VectorPurposexu1
Complexity on upper-level
xl1
Complexity on lower-levelxu2
Interaction with lower-levelxl2
Interaction with upper-level
Panel B: Decomposition of objective functions
Upper-level objective function
Lower-level objective function
Component
PurposeComponent
PurposeF1 (xu1 )Difficulty in convergence
f1 (xu1 , xu2 )Functional dependence
F2 (xl1 )Conflict / co-operation
f2 (xl1 )Difficulty in convergenceF3 (xu2 , xl2 )Difficulty in interaction
f3 (xu2 , xl2 )Difficulty in interaction(Sinha, Malo and Deb, 2014)
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Properties for inducing difficulties:
1. Controlled difficulty in convergence at upper and lower levels.
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

2. Controlled difficulty caused by interaction of the two levels.
3. Multiple global solutions at the lower level for a given set of upper level variables.
4. Possibility to have either conflict or cooperation between the two levels.
5. Scalability to any number of decision variables at upper and lower levels.

Controlling Difficulty for ConvergenceØ Convergence difficulties can be induced via following

routes:Ø Dedicated components: F1 (upper) and f2 (lower)Ø Example:

Quadratic

Multi-modal
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

6. Constraints (preferably scalable) at upper and lower levels.

Controlling Difficulty in Interactions

Next, we provide the bilevel test problem construction procedure, which is able to induce
most of theØdifficulties
suggested
above.variables x and x could be chosen
Interaction
betweenas follows:u2

l2

3.1 Objective functions in the test-problem framework§ Dedicated components: F3 and f3
To create Øa tractable
framework for test-problem construction, we split the upper and lower
Example:level functions into three components. Each of the components is specialized for inductionof certain kinds of difficulties into the bilevel problem. The functions are determined basedon the required complexities at upper and lower levels independently, and also by the requiredcomplexities because of the interaction of the two levels. We write a generic bilevel test problem
as follows:
F (xu , xl ) = F1 (xu1 ) + F2 (xl1 ) + F3 (xu2 , xl2 )f (xu , xl ) = f1 (xu1 , xu2 ) + f2 (xl1 ) + f3 (xu2 , xl2 )where
xu = (xu1 , xu2 ) and xl = (xl1 , xl2 )(3)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

In the above equations, each of the levels contains three terms. A summary on the rolesof different terms is provided in Table 1. The upper level and lower level variables have beenbroken into two smaller vectors (see Panel A in Table 1). The vectors xu1 and xl1 are used toinduce complexities at the upper and lower levels independently. The vectors xu2 and xl2 are
responsible to induce complexities because of interaction. In a similar fashion, we decompose
the upper and lower level functions such that each of the components is specialized for a certain
purpose only (see Panel B in Table 1). At the upper level, the term F1 (xu1 ) is responsible
Evolutionary Computation Volume x, Number x

5

18

DSf

5 June 2017

A. Sinha, P. Malo and K. Deb

can be made, whether it is useful to solve the lower level optimization problem at all for a givenxu .

Difficulty due to Conflict/Co-operation
Ø Dedicated components: F2 and f2 or F3 and f3 may be

The upper level constraint subsets, Gb depends on xl , and Gc depends on xu and xl . The
values from these constraints are meaningful only when the lower level vector is an optimal
solution to the lower level optimization problem. Based on the various constraints which may
be functions of xu , or xl or both, a bilevel problem introduces different kinds of difficulties in
the optimization task. In this paper, we aim to construct such kinds of constrained bilevel test
problems which incorporate some of these complexities. We have proposed four constrained
bilevel problems, each of which has at least one or more of the following properties,
Ø Obtain multiple lower-level optima for every upper level

Controlled Multimodality

solution:used to induce conflict or cooperation
Ø Examples:

1. Constraints exist, but are not active at the optimum§ Component used: f2

2. A subset of constraints, or all the constraints are active at the optimumØ Example: Multimodality at lower-level§ Cooperative interaction = Improvement in lower-level improves upperlevel (e.g. F2 = f2)§ Conflicting interaction = Improvement in lower-level worsens upper-level(e.g. F2 = -f2)
§ Mixed interaction is also possible

3. Upper level constraints are functions of only upper level variables, and lower level constraints are functions of only lower level variables

Induces multiple solutions:x1l1 = x2l1

4. Upper level constraints are functions of upper as well as lower level variables, and lower
level constraints are also functions of upper as well as lower level variables
5. Lower level constraints lead to multiple global solutions at the lower Bilevel
level Test Problems

Gives best UL solution:x1l1 = x2l1=0

6. Constraints are scalable at both levels
1.5

15

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

While describing the test problems in the next1 section, we discuss the construction proce1
0.5
dure for the individual constrained test
problems.
1.5
1.6
500

100

4

1.6

x l2

0.1

1.4

11

5
SMD
test
problems
1.2
x 4.3

0

0.5

5.5

l2

−1

4.1

4.3

4.5

x l2

−1.5
−1.5 −1−0.5 0 0.5 1 1.5

1

1.4

11
5.5

5

15

x

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

500

100

−0.5
4.3

1.2

4.1

4.3

1

4.5

l1
0.8principles introduced
By adhering5to the designin the previous section,5.5we0.8
now propose a set of
S: Lower level function contours
5.5
0.6
0.6
−0.4
−0.2 problem
0 0.2 0.4 represents a different
withtherespect
to lowerlevel
variables
twelve problems
SMD
test
problems.
Each−0.4 −0.2 0which
0.2 0.4 we call asx l1
at (x u1,x u2) = (0,0)
difficulty level inx l1terms of convergenceat the two levels, complexityof interaction between two
R: Lower level function contours
T: Lower level function contours
levelswith
andrespectmulti-modalities
at each30of the levels. The first eightproblems
arevariables
unconstrained andwith respect
to lower levelto lower level variables4
at (x u1,x u2) = (2,2)
at (x u1,x u2) =four(−2,2)are constrained.
the remaining
5

2

−0.6

Difficulty due to Constraints

5.5
5

4.1

SMD1
4.3
x l2

4.1

4.5
5.5

Constraints are included at both levels with one or more of thefollowing properties:
Ø
Ø
Ø

Ø

Ø
Ø

Constraints exist, but are not active at the optimum
A subset of constraints, or all the constraints are active at the
optimum
Upper level constraints are functions of only upper level variables,
and lower level constraints are functions of only lower levelvariables
Upper level constraints are functions of upper as well as lower levelvariables, and lower level constraints are also functions of upper aswell as lower level variables
Lower level constraints lead to multiple global solutions at the lower
level
Constraints are scalable at both levels
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

−1
−1.2

x u2

4

0

1

Problem 1
20

Interaction: −0.6
Cooperative
5.5

8

−0.8
4.5

−2

5

−0.8

Lower
level:−1Convex (w.r.t. lower-level variables)
4.3
xl2
4.1
4.5

Upper level:−1.2Convex (induced space)
4.5

5.5
11
This is a simple
test problem
where the lower level problem
is 11a convex
optimizationtask, and
−1.4
−1.4
−4
100
100
500
the upper levelis convex−1.6with respect to upper level variables 500
and optimal
lowerlevel variables.
−1.6Upperand Lower Function Contours−0.4 −0.2 0 0.2 0.4−4 −2 02
4
−0.4 −0.2 0 0.2 0.4
The two levels cooperatewith each other. x u1
x l1
x l1

U: Lower level function contours
P: Upper level function contours!
p respecti to upper
2 level variables
with respect to lower level variables
with
F1 = !
u1 )
i=1 (xlower
at (x u1,x u2) = (−2,−2)
at optimalq
i 2level variables

Q: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,−2)
500

1.5

15

1
1

1.6

1.5

x l2

0.5
0

1.6

500

F2 = !i=1 (xl1 )
1.4
−0.5
1.4
!r
r
1.2
−1
F3 = ! i=1 (xiu2 )2 + i=1 (xiu2 − tan xil2 )2 x
1.2
x l2
(12)
l2
−1.5
p
1
Figure 3: Upper and lowerf level
functionforafour-variable
SMD1
test
problem.
i contours
2
1−1.5 −1−0.5 0 0.5 1 1.5
1 = !i=1 (xu1 )
x l1
0.8
0.8
q
i 2
S: Lower level function contours
f2 = !i=1 (xl1 )
0.6
0.6
−0.4
−0.2
0
0.2
0.4
with
respect
to
lower
level
variablesr−0.4 −0.2 0 0.2 0.4
x
at
(x
,x
)
=
(0,0)
f3 = i=1 (xiu2 − tan xil2 )2
x l1
l1
u1 u2
T: Lower level function contours
R: Lower level function contours
The range of variables is as follows,with respect to lower level variables
with respect to lower level variables
4
10
Evolutionary Computationx, Number x
at (x u1,x u2) = Volume(−2,2)
at (x u1,x u2) = (2,2)
−0.6
2
−0.6
xiu1 ∈ [−5, 10], ∀ i ∈ {1, 2, . . . , p}
−0.8
−0.8
x u2
0
i
xu2 ∈ [−5, 10], ∀ i ∈ {1, 2, . . . , r}
−1
−1
xl2
x l2
(13)
−2
−1.2
−1.2
xil1 ∈ [−5, 10], ∀ i ∈ {1, 2, . . . , q}
−1.4
−1.4
π
−4
,
),
∀
i
∈
{1,
2,
.
.
.
,
r}
xil2 ∈ ( −π
−1.6
2
2
−1.6
100

0.1

0.5

100

11

11

5

4.3

4.3

15

4.1

4.3

5.5

5

5.5

4.1

4.3

4.5

4.5

5

5

5.5

5.5

30

5.5

5.5

8

5

5

4

4.5

4.3

4.5

1

4.3

4.1

4.5

5.5

20

11

0

x l1

0.2 0.4

100

500

−4

−2

0

x u1

2

4

P: Upper level function contours
U: Lowerfunction
Relationship between upper level variables and lower level optimal variables
is levelgiven
ascontours
follows,xil1 = 0, ∀ i ∈ {1, 2, . . . , p}
xil2 = tan−1 xiu2 , ∀ i ∈ {1, 2, . . . , r}

5.5

11

100

500

−0.4 −0.2

4.1

4.5

with respect to lower level variables with respect to upper level variables
at (x u1,x u2) = (−2,−2)
at optimal lower level variables−0.4 −0.20x l1

0.2 0.4

Q: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,−2)(14)The values of the variables at the optima are xu = 0 and xl is obtained by the relationship given
above. Both the upper and lower level functions are equal to zero at the optima.
Figure 3 shows the contours of the upper and lower level functions with respect to theupper and lower level variables for a four-variable test problem. The problem has two upper
level variables and two lower level variables, such that the dimensions of xu1 , xu2 , xl1 and xu2
are all one. Sub-figure P shows the upper level function contours with respect to the upper
level variables, assuming that the lower level variables are at the optima. Fixing the upper levelvariables (xu1 , xu2 ) at five different locations, i.e. (2, 2), (−2, 2), (2, −2), (−2, −2) and (0, 0),
the lower level function contours are shown with respect to the lower level variables. This showsthat the contours of the lower level optimization problem may be different for different upper
level vectors.

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

19

at (x u1,x u2) = (−2,−2)

at optimal lower level variables

at (x u1,x u2) = (−2,2)!
f2 = !qi=1 (xil1 )2r
The range of variables is as follows,
f3 = i=1 (xiu2 − log xil2 )2

l1
xil2 ∈ (0, e],12∀ i ∈ {1, 2, . . . , r}

12

−1.5

4.5

1.5

−0.5

0.2

x l1

0.5

1

0.4

T: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (−2,2)

1.5

x l2

5

−0.4

−0.2

0

0.2

x l1

0.4

4

1

xiu1 ∈[−5, 10], ∀ i ∈ {1, 2, . . . , p}
xiu1 ∈ [−5, 10], ∀ i ∈ {1, 2, . . . , p}
xiu2x∈i [−5, 10], ∀ i ∈ {1, 2, . . . , r}
∈ [−5, 10], ∀ i ∈ {1, 2, . . . , r}u2
xil1 x∈i [−5,10],q}10], ∀∀ i i∈∈ {1,{1, 2,
2, ......,,q}l1 ∈ [−5,−ππ π ∀ i ∈ {1, 2, . . . , r}xil2 x∈il2 (∈−π2( ,2 2, ),2 ), ∀ i ∈ {1, 2, . . . , r}

0.3

4.5

0.2

4.1

4.01

0.1

7.5

5

5.5

−0.2

0

0.2

0.1

1.4

6

6

0

2

2

25

1.3

4.1

10

6

−1.5 −1 −0.5 0

0.5

−1.5

−1

−0.5

0

0.5

x l1

1

S: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (0,0)

1
1.5

4

30

1.4

x l2

6

6

5

1.3

x u2 (19)
(19)

1.2

Q: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,−2)i= 0,∀ ∀i ∈i ∈{1,{1,2,2,. .....,,q}q}xil1 x=il1 0,−1 i 2= tan{1, 2, . . . , r}−1 (xxil2 x=l2 tan(xiu2u2)2), , ∀∀ ii ∈∈ {1,2, . . . , r}

−1

−0.5

−2

20

−0.5

1.3

x l1

0.5

1

1.2
1.1
1
1.5

1.5
15

1.4

9
4.1

xl2

6

6

6

5

1.3
1.2

9

1.1

−1

0

25

0

4
1

9

−1.5

1.4

R: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,2)

8

15
9
4.1

−1.5

2

1.5

6

6

9

T: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (−2,2)
25

6

5

−1.5
1.5

1

1.5

15

9

−0.5
−1

0

0.5

1

1.1

−4

1
1.5

−4 −2
Relationshipbetweenupper
level
variables
andlower
lowerlevel
level optimal
is given
as follows,
Relationshipbetweenupper
level
variablesandoptimalvariables
variables
is xgiven
as follows,
l1

0.4

x l1

with respect to upper level variablesat optimal lower level variables

1

15

5

0.5

2

1

1.1

r
i 2
i 2
i=1 ((xu2 ) − tan xl2 )The range of variables is as follows,

5

−0.4

U: Lower level
function contours
Evolutionary Computation
Volumex, NumberP: xUpper level function contours
with respect to lower level variables
at (x u1,x u2) = (−2,−2)

Q: Upper level function contours

The range of variables is as follows,

0.4

xl2

−4

0.4

6.5

Problem 3

5.5

−2

20

0.2

0.2

7.9

level is convex with respect to upper level variables and optimallevelConvex
variables.(induced space)
Upperlower
level:
!p
i 2
=
(x
)
level is convex withFrespect
to
upper
level
variablesandoptimallower
level
variables.
1!qi=1 u1Upper and Lower Function Contours
F2 = !i=1!p(xi )i2 2 !
r
F1 =r!i=1l1
i(xu1
2)
i 2
i 2
F3 =
q(xu2 i) 2+
i=1 ((xu2 ) − tan xl2 )
F2!
=pi=1
(x
)
l1
i=1
i
2
!(x
!r
x l2(18)
r u1 )i 2
f1 =F =i=1
i 2
i 2
(x"
3
u2
#)2 i+$2 i=1 ((xu2 ) i−%tan xl2 )
!i=1
!
q
(18)
(xiu1 "
)xl1 − cos 2πxl1%
f2 =f1q=+ pi=1
i=1
x l2
x
#
$
!
l2
!r
2
q
i
2 xi
q +((xiu2
cos
x l1
f3 =f2 =i=1
tan−xil2)22πxl1l1i=1) −
!

0.6

5.5

0

7

LowerSMD2
level:testMultimodality
using Rastrigin’s function
Figure 6: Upper level function contours for a four-variableproblem.

0.5−4 −2x 0
2
Evolutionary Computation x Volume x, Number
x u1
l1

7.99

7.5

u1 u2
Interaction:
Cooperative

u1 u2

f3 =

2
−0.2

0

4

0.1

7.5

P: Upper level function contours

U: Upper level function contours

0.3

7.5

Q: Upper level function
contours
0.1
with respect to lower level variables
−0.2
0
0.4
at−0.4(x u1,x u2) =0.2(2,−2)x l1with respect to lower level variables
with respect to lower level variables with respect to upper level variables
Figure 6:Upper level functionat contours
for a four-variable
test problem.
at (x ,x )SMD2= (2,−2)
at (x ,x ) = (−2,−2)
optimal lower level variables

R: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,2)

1

(16)

0.2

4.1

4.01

5

5.5
−0.4

4

2

0.3

4.5

6.5

x l1

0.1

0.5
0.4
0.4

9

6

4.5

4

(16)

x u2

0.4

xl2

−2

0.2

1.2

8

8

0.5

4

0.6

6.5

6.5

0

6

10

4.1

0.6

5.5

2

−0.2

4.1

12

4.01

30

5

0

x u1

P: Upper level function contours−4with respect to upper level variables−4 lower−2 level
0 variables
2
4
at optimal
x u1

7.5

7

9

14

x l2

S: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (0,0)

4

5

0

0

−2
20

7

−0.4

5 June 2017

0.2

7.9

7.99
7.5

0

25

16
4.5

x l1

2
−0.2

−1

0.2

7.9

4

0.5
6.5

1.5

18

1

(15)

−4

0.3

7.5

1

0.6

0.4

1.5

20

5

0.5

6

5.5

xiu2 i∈ [−5, 1], ∀ i ∈ {1, 2, . . . , r}
∈ [−5, 10], ∀ i ∈ {1, 2, . . . , p}u1 [−5,xil1x∈
10], ∀ i ∈ {1, 2, . . . , q}
xiu2 ∈ [−5, 1], ∀ i ∈ {1, 2, . . . , r}xil2x∈i (0, e], ∀ i ∈ {1, 2, . . . , r}
∈ [−5, 10], ∀ i ∈ {1, 2, . . . , q}

0.5

x u2

0.4

U: Upper level function contours 0.1
with respect to lower level variables−0.4 −0.2
00.2
0.4
at (x u1,x u2) = (−2,−2)
x l1
7

x l1

0.2

1

2

8
4.1

l1

0

2

−4

8

0.5

4

7

2
−0.2

0.4
R: Upperlevel function contours
7
xwith
respect to lower level variables
0.3
l2
at (x u1,x u2) = (2,2) 7.5

4
−2

0.6

6.5

0.4

6

7.5

6.5

−0.4

3

2.5

14

4.01

x l2 x

0.2

7.9

1
30

20

with respect to lower level variables
at (x u1,x u2) = (2,2)
7.99

0

4

0.2

6.5

07

4

S: Upper level function contours
2with respect to lower level variables
at (x8 u1,x u2) = (0,0)

10

3
1.5

1

0.1

12

−0.4

The range of variables is asfollows,xiu1∈ [−5, 10], ∀ i ∈ {1, 2, . . . , p}

(15)

16

10

−0.2

7.99

3.5

4.5

0.5

0.1
7

4

18

x l1

7.9

7.99

Problem 2

x l2

2

0.4

7.5

−0.4

upper level variables and optimal lower level variables. Since, the two levels are conflicting,!pi lead2
an inaccurate lower level
optimummay
to upper level function value better than the trueF1 =
i=1 (xu1 )!
Upper and Lower Function Contours
q
optimum for the bilevel
F2problem.
=−(xi )2
20

4

0.2

x u2
T: Upper level function
0.4 contours
7with respect to lower levelvariables
0.3
at (x u1,x u2) =7.5(−2,2)x l2This test problem is similar to the SDM1 test problem, however there is a conflict between theupper level and lower level optimization task. The lower level optimization problem is once
4.2 SMD2
again a convex optimization task and the upper level optimization is convex with respect toInteraction:
Conflicting
upper Thisleveltest
variables
optimallower
level
Since,
the twolevelsareconflicting,problem andis similar
to theSDM1test variables.
problem, however
there
is a conflict
betweenthe
an inaccurate
lower
may leadto upperlevellevel
functionvalue
betterthan
thetrue lower-level variables)
upper level
and level
lower optimum
level optimization
task.
The lower
optimization
problemis onceLowerlevel:
Convex(w.r.t.
again
convexoptimizationis convex
respect (inducedto
optimum
fora thebilevelproblem.task and the upper level optimization
Upperlevel:with
Convexspace)

50

6.5level function contours at different (xu1 , xu2 ), i.e. (2, 2), (−2, 2), (2, −2), (−2, −2) and (0, 0).
From sub-figures Q, R, S, T and V, we observe that if the lower level variables move away fromSMD2
its optimal location, the upper level function value deteriorates. This means that the upper level
function and the lower level functions are cooperative.

!r i=1 i l12 !r!p (xu2i) 2− i=1 (xiu2 − log xil2 )2
F3 = ! i=1
F1 = p !
)i=1 i(xu1
f1 =(xqu1(x)2i )2
F2!
= i=1−
q! i=1l1!rr(xi )i2 2
f2 =
i
i 2
l1
F3!
= i=1
(x
)
r
!pi=1 i iu2 2 − ii=12(xu2 − log xl2 ) x l2
f3 =
(x(x
−) log xl2 )f1 = i=1i=1
u2u1

−0.2

x l1

6
7

0.6

DSf

4.2

7.9

7.5

6.5
−0.4

30

8

7.99

at (x u1,x u2) = (2,−2)level function contours at different (xu1 , xu2 ), i.e. (2, 2), (−2, 2), (2, −2), (−2, −2) and (0, 0).
From sub-figures
Q,4:R,Upper
S, T level
and V,
we observethatlower levelvariables
move away from
Figurefunction
contours
forifa thefour-variable
SMD1
test problem.
its optimal location, the upper level function value deteriorates. This means that the upper level
function and the lower level functions are cooperative.

U: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (−2,−2)

0

x u1

2

4

P: Upper level function contours
with respect to upper level variables

optimal lower level variables(20)at(20)

−1.5

−1

−0.5

0

0.5

1

1
1.5

x l1
Q: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,−2)The values of the variables at the optima are xu = 0 and xl is obtained by the relationship given

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

The valuesof Both
the variables
thelower
optimaarefunctions
xu = 0are
andequal
xl istoobtained
byoptima.
the relationshipabove.
the upperatandlevel
zero at the
Rastrigin’sgiven
above. function
Both the
upper
level
are equal
to zeroat the which
optima.
Rastrigin’s
used
in f2andhas lower
multiple
localfunctions
optima aroundthe global
optimum,
introduces
functionused in fdifficulties
locallevel.
optima around the global optimum, which introduces
convergenceat the lower
2 has multiple
convergenceSub-figure
difficulties
at the lower level.
P in Figure 7 shows the contours of the upper level function with respect to the

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

upper levelPvariables
assuming
thethelower
level variables
be optimaleach xu .with
Sub-figures
Sub-figure
in Figure7 shows
contoursof the toupperlevel atfunction
respectQ,to theupper level
to be optimal
at each xu . Sub-figures
Q,
14 variables assuming the lower level variables Evolutionary
Computation Volumex, Number x

A. Sinha, P. Malo and K. Deb

14

Evolutionary Computation

Interaction: Conflicting

Results Using BLEAQ

Lower
level: Multimodality using Rastrigin’s function
is convex with respect to upper level variables and optimal lower
level variables.
A. Sinha, P. Malo and K. Deb

Problem 4Upper level: Convex (induced Space)!pF1 = i=1 (xiu1 )2
is convex with respect to!
upperlevel variables and optimal lower level variables.
q
Upper and Lower Function Contours
F2 = −(xil1 )2!r i=1!pi )2 i− 2!r (|xi | − log(1 + xi ))2F3 = !
u2 (xu1 )u2l2
F1pi=1
= (x!
i=1
i=1
i q2 i 2(21)
f1 = F2i=1) (xl1 )= (x− u1i=1"%!rx l2#i i)2$−!!
ii2
2q r (x3 =!
u2 | i− log(1 + xl2 ))i=1 u2f2 = qF+x− i=1
cos(|x
2πx
p
l1
i=1
i l12
(21)
f1r= i=1 (xu1 "
)
!
%
i!
i
2
x l2
x
#
$
2
l2
q
f3 = f i=1
l2 ))= q(|x+ u2 | − log(1xi +−xcos
2πxi

u

5

5

6

6

5

5

2

1

2

2

8

0.1

1

1

5

6

1

10

6

6

5

9

5

8

0

7

7

2

f3 =

l1
l1
i=1
i
i
2
i=1 (|xu2 | − log(1 + xl2 ))

xiu1 ∈ [−5, 10], ∀ i ∈ {1, 2, . . . , p}i
∈ [−5,∈ {1,, p}xiu2 ∈xiu1[−1,1], 10],∀ i ∀∈ i{1,2, .2,. ...,.r}i ∈ {1, 2, . . . , r}u2 ∈ [−1,xil1 ∈x[−5,10], 1],∀ ∀i ∈{1, 2, . . . , q}
i
x
∈
[−5,
10],
∀
i
∈
{1,
2,
.
.
.
,
q}
l1
xil2 ∈x[0,i e], ∀ i ∈ {1, 2, . . . , r}
∈ [0, e], ∀ i ∈ {1, 2, . . . , r}

4.1

6

−0.5

4

6

6

−1

0

0.5

x l1

T: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (−2,2)
5

6

6

6
5

l2

4

6

−0.5

0

0.5

1

3

U: Lower level function contours
with respect to lower level variables(23)
at (x u1,x u2) = (−2,−2)

0.5

4
3

1

R: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,2)
5

6

6

6

10
9

5

5

xl2

8
7
6

5

5

−4

4

6

6

0

x u1

2

4

P: Upper level function contours
with respect to upper level variablesat optimal lower level variables(23)

The values of the variables at the optima are xu = 0 and xl is obtained by the relationship given
the upper
level
equal
at the optima.
The valuesabove.
of theBoth
variablesat andthe lower
optimaarefunctions
xu = 0areandxl to
is zeroobtainedby the relationship given

above. Both theupper
and lowerthelevelareas equal
to zerothe optima.bilevel probFigure
8 represents
samefunctions
informationin Figure
7 for ata four-variablelem. However, this problem involves conflict between the two levels, which make the problem
Figure8 represents the same information as in Figure 7 for a four-variable bilevel probsignificantly more difficult than the previous test problem. For this test problem if a lower levellem. However,this problem
betweentwo levels,
which
problem
optimization
problem involves
is stuck at aconflict
local optimum
for thea particular
xu , thenit willmake
end upthehavingsignificantly
moreobjective
difficultfunction
than theprevioustest problem.
testattainproblema lowera bettervalue
at the upper
level, than For
whatthis
it willat theiftrue
global level
lower
level optimum.
even
if anotherfor
lower
lower levelxoptimization
problem
optimization
problemis stuckTherefore,
at a local
optimuma particular
end isupsuchaving
u , then it will
cessfully solvedin thevicinityof xupper
inaccurate
dominatenewu , the previous
a better objectivefunctionvalue
at thelevel, thanwhat solution
it will willattainat the thetrue
globalsolution
at
the
upper
level.
This
problemcanbehandled
only
by
those
methods
which
are
able
lower level optimum. Therefore, even if another lower lower level optimization problem is sucto efficiently handle lower level multi-modality without getting stuck in a local basin.
cessfully solved in the vicinity of xu , the previous inaccurate solution will dominate the new
solution at the upper level. This problem can be handled only by those methods which are able
4.5 SMD5
to efficiently
handle lower level multi-modality without getting stuck in a local basin.

sfdsFDSA

0

5

Relationshipuppervariables
level variables
lower
leveloptimal
optimal variables
is given
Relationshipbetweenbetween
upper level
andandlower
level
variables
is given
as follows,−4 −2
x l1as follows,
i

−2

4.1

−1

= 0, ∀ i ∈ {1, 2, . . . , q}
xil1 = x0,l1∀ i −1∈ {1,2, . . . , q}ixil2 =−1log i |xu2 | − 1, ∀ i ∈ {1, 2, . . . , r}xil2 = log|xu2 | − 1, ∀ i ∈ {1, 2, . . . , r}

−0.5

x l1

0

20

5

6

6

−1

2
4
1

Number of Runs: 21
Savings: Ratio of FE required by nested approach against BLEAQ

4.1

6

8

8
u2
(22)
7

6

5

1.5

30

(22)
x

6

5

1

10
9

5

x l2

0.5

S: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (0,0)

3

1

0

x l1

5

!r

The range of variables is as follows,

The range of variables is as follows,−1.5 −1 −0.5

65

Following are the results for 10 variable instances of the test problems(Sinha et al., 2014) using BLEAQ
Comparison performed against nested evolutionary approach

3

2

10
9

u

4

3

5

6

Volume x, Number x

4.1

6

−1

−0.5

4

6

6

0

0.5

1

3

x l1
Q: Lower level function contours
with respect to lower level variables
at (x u1,x u2) = (2,−2)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

For other problems as well, the improvement is more than an order of magnitude
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

20

SDM1
SDM2
SDM3
SDM4
SDM5
SDM6

DSf

Results on SMD1

Convergence Plots on SMD1

2

2

1.5

Table
9: Accuracy
forthethelower
upperlevel
andcalls
lowerfromlevels, and the lower level calls from
Table 9: Accuracy for the upper andlowerlevels, and11 runs of the proposed BLEAQ.
11 runs of the proposed BLEAQ.−1.5
−2
−2

−1.5

−1

−0.5

0
x4u

0.5

1

1.5

2

xu

0

F

10

10

−4

10

0

−4

50

100

150

200

250

300

350

400

450

500

10

550

2

0

50

100

150

200

250

300

350

400

450

500

50

100

150

200 250 300 350
Upper Level Generations

400

450

500

2

10

10

0

0

10

10
0

True Relation
Gen. 1
Gen 150
Gen. 450
Gen. 550
Gen. 610

−1

0

−2

Lower Level10−2
Function Value
f

−0.5

10
Upper Level
Function Value
−2

0

10

F0

Bilevel optimum

0

10

f0

1
0.5

2

10

Progress path for the elite member

SMD1 Quadratic RelationshipConvergence x4lxl*

LL Accuracy LL Calls LL Evals
LL Calls
0.003521
528
5 June 2017 202.47
0.002745
522
176.090.004364
603
225.910.002716
574
146.390.003773
513
243.680.000000
167
50.24

UL Accuracy
0.006828
0.003262
0.009122
0.006957
0.0041030.000000

−2

10

−4

10

0

−4

50

100

150

200 250 300 350
Upper Level Generations

400

450

500

10

550

0

Pr.
No. MedianMedianMedianMedianMedian MedianConvergence Plot for SMD1
LL Evals
LL
Evalswithapproximation
atoptima(0,0)
improves
UL
Accuracy
LL
Accuracy
LL
Calls
UL Accuracy Quadratic
LL
Accuracy
LL
Calls
Figure 12: Quadratic relationship convergence.
LL Calls
LL Calls
CEC-2017, San Sebastian, Spain
CEC-2017, San Sebastian, Spain
generations
TP1
0.000000
0.000000(100.0)
206
72.76
TP1
0.000000 (225.0)increasing
0.000000(100.0) (225.0) 206
Ankur72.76
Sinha and
Kalyanmoy Deb
Sinha and Kalyanmoy Deb
Figure 10: Convergence plot forAnkurSMD1.
Figure 11: Convergence plot for SM
TP2
0.012657 (0.0)
0.0001260.012657(100.0) (0.0) 235
61.79(100.0)
TP20.000126
235
61.79
TP3
0.000000 (-18.678711) TP3
0.0000000.000000(-1.015625)
112
40.00(-1.015625)(-18.678711)
0.000000112
40.00
also provides the median number of lower level calls, and the average number of
TP40.040089 (-29.2)
0.0077590.040089(3.2)
60.00(3.2)
TP4(-29.2) 255
0.007759
255
60.00
lower level function evaluations required per lower level call. Table 10 comparesapproximations generated at various generations. It can be observed thatTP5
0.008053(-3.6)function evaluations
0.0400630.008053(-2.0)
78.50
TP5(-3.6)
0.040063(-2.0)
78.50
the meanat the upperand 203lower levels
requiredby BLEAQ 203
approximations in the vicinity of the true bilevel optimum improves with
TP6
0.000099(-1.2091)
0.000332(7.6145)75.23(-1.2091)(7.6145) times 233
75.23
againstthat requiredTP6
by WJL.0.000099
WJl requires
close233
to an 0.000332
orderof magnitude
creasing number of generations.
TP70.093192
0.093192(1.98)
3862
95.42
TP7
0.093192(-1.98)and
0.093192(1.98)
95.42
more(-1.98)
function evaluations
at thelower level,
two ordersof magnitude
times 3862
Advanced Topics of EBO
TP80.001819
0.000064(100.0)61.50
TP80.001819(0.0)on61.50
more(0.0)
function evaluations
at theupper level,for200
mostof0.000064
theTesttest (100.0)
problems. This 200
Overall
Results
Eightclearly demonstrates the efficiency gain obtained using the BLEAQ approach.
oMulti-objective
EBO for constrained test problems
8.3 Results
Problems
It also suggests that the mathematical insights used along with the evolutionary
results forapproacheight bilevelproblems
nAt least
onesub-section,level has multiple
objectives
principles inMedianthe BLEAQ
is testhelpfulin converging quickly towards the
In thiswe provide
results for 8 standard constrained test probl
Table 10: Comparison of BLEAQ
againsttheComparison
results
achieved
by WJLapproach.
Table
10:of BLEAQ
againstthe
Comparison
againsttheevolutionary
algorithmof Wang
etal.results(2005)achieved by WJL approach.
bilevel optimal
solution.
chosen from the literature. We compare our results against the approach
BLEAQ is an order of magnitude better
Pr. No.

nnoPr. No.
TP1
TP2
TP3
TP4
TP5
TP6
TP7
TP8

9

Mean UL Func. Evals.
Mean ULLL Func.
Func. Evals.
Evals.
Pr. No.
Mean
Mean LL Func. Evals.
BLEAQ
WJL
Savings BLEAQ
BLEAQ
WJL levelSavings
Savings
WJL
WJL
Savings
Table 8: Function
evaluations(FE)
for the upper(UL) andBLEAQ
the lower level
796
85,49915,43285,4995.54
TP1796BLEAQ.
85,499107.41
15,43285,499
5.54(LL) from
11 runs of107.41
the proposed
1,578
256,227
162.37
15,632
256,227
16.39
TP2
1,578
256,227
162.37
15,632
256,227
16.39
No. Best Func.
Median Func.
Evals. 224.58
Worst Func.
Evals. 92,526
412 Pr. 92,526
224.5892,52619.10
TP3 Evals. 4844
412
92,526
4844
19.10
UL
LL
UL
268
291,817 LL 1088.87
291,81717.77
TP4 UL 16,422
268 LL 291,817
1088.87
16,422291,81717.77
TP115041 77,302
780
24658 15,524
1348
1,214
77,302 14115 63.68
77,302
4.98
TP5 718 15,524
1,214
63.68
77,302
4.98
TP2
12524
1430
14520
1434
16298
2586
296
163,701
553.04
17,421
163,701
9.40
TP6
296
163,701
553.04
17,421
163,701
9.40
TP3
4240
330
4480
362
6720
518
4,144
1,074,742
259.34257,243
1,074,742
4.18
TP7
4,144
1,074,742
259.34257,243
1,074,742
4.18
TP4
14580
234
15300
276
15480
344
1,572
213,52210150135.85
213,52217.04
TP8 482 12,533
1,572
135.85
213,52217.04
TP515700 213,522
1302
15936 12,533
1564
TP6
TP7
TP8

Conclusions

14667
234622
10796

9

230
3224
1288

17529
267784
12300

Conclusions

284
4040
1446

21875
296011
18086

356
5042
2080

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

In this paper, we propose an efficientbilevelevolutionary(BLEAQ)In thispaper,
we proposealgorithm
an efficientbilevel evolutionary algorithm (BLEAQ)
which works by approximating thewhich
optimalsolution
mapping between
the lower
works
by approximating
the optimal
solution mapping between the lower
levelsfdsFDSA
optimal solutions and the upper
level variables.
onlylevel optimal
solutionsTheandalgorithm
the uppernot
levelvariables. The algorithm not only
converges towards the the optimalconverges
solution to
the bilevel
optimization
problem,towards
the theoptimal solution
to the bilevel optimization problem,30
but also provides the optimal solution
mappingclose
the optima,
which
pro- close to the optima, which probut also
providestheto
optimalsolution
mappingoMEBO with decision-making
posed by Wang et al. (2005). The reason for the choice of this approachoMany-objective
EBO, parallel EBO, multi-modal
benchmark is that the approach was successful in solving all the chosen
EBO, meta-modeling
EBO The results obtained using the BLEAQ and WJL
strained test problems.
approachhas
beenTables 8, 9 and 10. Table 8 provides the moRobust EBO: Uncertainty inprovided
at least oneinlevelmum, median and maximum function evaluations required to solve the choEBO applications
problems using the BLEAQ approach. Table 9 provides the accuracy obta

nParameterof algorithms
at bothtuning
the levels,in terms of absolute di↵erence from the best known solu
to a applications
particular test problem. The numbers in the brackets provide thenPracticalsolution known from the literature for each of the test problems. The t
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

29

21

DSf

5 June 2017

Advanced EBO Ideas (cont.)

Multi-objective ExtensionoHighly constrained EBO
oMixed-integer EBO
oEBO with a fixed budget at LL and ULoEBO versus EO for F=f
oError propagation from lower level to upper
level• Bilevel problems may involve optimization of multiple objectives at one
or both levels• Dempe et al. (2006) developed KKT conditions• Little work has been done in the direction of multi-objective bilevel
algorithms (Eichfelder (2007), Deb and Sinha (2010))• A general multi-objective bilevel problem may be formulated asfollows:

nTheoretical convergence studies

oEvolutionary Multi-Level Optimization (EMLO)
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

LeaderFollowerobj 1

LeaderMultiple objectives involved atboth the levels

LeaderFollower

obj 1

obj 2

Objectives: Max Objective 1

Max Objective 2
Followers

Max Objective 2

obj 1
Obj 1

Followers

obj 1

Objectives: Max objective 1

obj 2

Objectives: Max objective 1

Max objective 2
obj 1

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Two levels of decision making•

LeaderObjectives: Max Objective 1

Max objective 2

•

obj 2

Multiple objectives involved atboth the levels

Obj 1

obj 2

Two levels of decision making

•

obj 2

•

Pessimistic Multi-objective
obj 2

Optimistic Multi-objective

obj 1

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

22

DSf

5 June 2017

Uncertainty from Unknown
Preference Structure

LeaderFollowerobj 1

LeaderTwo levels of decision making•

Multiple objectives involved atboth the levels

Leader

obj 1

obj 2

Objectives: Max Objective 1

Max Objective 2
Followers

Max Objective 2

obj 1
Obj 1

Followers

obj 1

Objectives: Max objective 1

obj 2

Objectives: Max objective 1

Max objective 2

Obj 1

obj 1

Lower level problem becomes single objective

obj 1

There is uncertainty around the frontier(Sinha et al., 2015)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Challenges

Test problem 1 and results• Such problems can be very difficult to handle• Optimistic formulation makes little sense in these
problems• Considering a known preference structure (andaccounting for uncertainties) might be a realistic andviable approach

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Follower

LeaderObjectives: Max Objective 1

Max objective 2

•

obj 2

Multiple objectives involved atboth the levels

obj 2

Two levels of decision making

•

obj 2

•

obj 2

Preference Structure Known

x = (xu, xl)

xu = (x)xl = (y)• Lower level Pareto front depends on x
• Upper level Pareto-optimal front lies on
constraint G1• Maximum two solutions from each x• Not all x in upper Pareto-optimal front• Solutions possible even below the upper
level Pareto-optimal front, but they are
infeasible(Eichfelder, 2007)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

23

DSf

5 June 2017

BLEMO

(Deb and Sinha, ECJ 2010)

Population structure
Lower and upper level
NSGA-II
ArchivingIter = 2

Both levels use NSGA-II iteratively

Iter = 3(Deb and Sinha, 2010)

x

y2

y1

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

A Business DM Problem
CEO: Leader and Dept Head: follower(Zhang et al, 2007)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Mine Taxation Strategy Problem from
FinlandKuusamo has natural beauty and a famous tourist resorto Contains large amounts of gold deposits
Dragon Mining is interested in mining in the region
Pros:o Generate a large number of jobs
o Monetary gains
Cons:

Weighted sum
solution (Zhang etal, 2007) is anextreme solution

o Run-off water from mining will pollute Kitkajoki rivero Ore contains Uranium, mining may blemish reputationo Open pit mines located next to Ruka slopes will be a turn-off forskiing and hiking enthusiasts
o Permanent damage to the nature
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

24

DSf

−500

−500

−600

−600

−700

−700

a=3

−800
−900
−1000

5 June 2017

−800
−900

a=4
0

500 1000 1500 2000 2500 3000 3500 4000

Fig. 4. Approximate Pareto-frontier for the extended model taking
all technologies into account.

−1000
0

500 1000 1500 2000 2500 3000 3500 4000

Fig. 5. Approximate Pareto-frontiers for the individual technologies
considered one at a time.

EMBO Test Problem
Construction Principle

BLEAQ Results
42

22
a=2

40

38

362.3 <= D <= 399.8

16
14
12
10
8
1

a=2
2650.0 <= R <= 2776.8

2650.0 <= R <= 2776.8
18

Tax per unit of metal

Quantity of Metal Produced

Environmental
Damage20

Difficulties
identified

362.3 <= D <= 399.8

36

Bottom-up
approach34

32

a denotes
technologies
2

3Time Period

30

4

5

Fig. 6. Approximate Pareto-frontier for the extended model taking all
Leader’s profit
technologies into account.

28
1

2

3
Time Period

45Taxationstrategies
Fig. 7.
Approximate
Pareto-frontiersinforpreferred
the individual technologies
region.
considered
one at a time.

Preferred strategy: ~75% profit to the government,
VIII.company
ACKNOWLEDGMENTS[7] R. F. Conrad and B. Hool. Resource taxation with heterogeneous~25% toThe authors wish to thank the Academy of Finland andthe Foundation of the Helsinki School of Economics forsupporting this study.
R EFERENCES[1] E. Aiyoshi and K. Shimizu. Hierarchical decentralized systems andits new solution by a barrier method. IEEE Transactions on Systems,
Man, and Cybernetics, 11:444–449, 1981.
[2] J. Bard. Practical Bilevel Optimization: Algorithms and Applications.
The Netherlands: Kluwer, 1998.
[3] J. Bard and J. Falk. An explicit solution to the multi-level programming
problem. Computers and Operations Research, 9:77–100, 1982.
[4] L. Bianco, M. Caramia, and S. Giordani. A bilevel flow model forhazmat transportation network design. Transportation Research Part
C: Emerging technologies, 17(2):175–196, 2009.
[5] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel
optimization. Annals of Operational Research, 153:235–256, 2007.
[6] R. F. Conrad. Output taxes and the quantity-quality trade-off in themining firm. Resources and Energy, 3(3):207 – 221, 1981.

Scalable in terms of variables andobjectives
Controllable difficulties

Some
Problems

quality and endogenous reserves. Journal of Public Economics,
16(1):17 – 33, 1981.
Sebastian,Spain[8] K. Deb and A. Sinha.CEC-2017,
An efficient San
and accurate
solution
methodology
Ankur Sinha
and Kalyanmoy
Deb a hybrid
for bilevel multi-objective
programming
problems using
evolutionary-local-search algorithm. Evolutionary Computation Journal, 18(3):403–449, 2010.
[9] S. Dempe, J. Dutta, and S. Lohse. Optimality conditions for bilevel
programming problems. Optimization, 55(5âĂŞ6):505âĂŞ–524, 2006.
[10] W. Halter and S. Mostaghim. Bilevel optimization of multi-component
chemical systems using particle swarm optimization. In Proceedingsof World Congress on Computational Intelligence (WCCI-2006), pages
1240–1247, 2006.
[11] J. F. Helliwell. Effects of taxes and royalties on copper mining
investment in british columbia. Resources Policy, 4(1):35 – 44, 1978.
[12] J. Herskovits, A. Leontiev, G. Dias, and G. Santos. Contact shape
optimization: A bilevel programming approach. Struct Multidisc
Optimization, 20:214–221, 2000.
[13] R. R. Pakala. A study on applications of stackelberg game strategies
in concurrent design models, 1993.
[14] S. Ruuska and K. Miettinen. Constructing evolutionary algorithms
for bilevel multiobjective optimization. In 2012 IEEE Congress on
Evolutionary Computation (CEC-2012), 2012.

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Five-step
procedure
Conflict between
lower and upper

levelsCEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

EMBO with Decision-Making
oPreference in LL
Pareto front may notlead to UL Pareto
solutionsoConverse is not trueoRaises interestinghierarchy among ULinteresting scenarios,and LL decision- Raises
which we are currently pursuing!
makersCEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

25

DSf

5 June 2017

Importance of LL Decision-Maker• LL Decision-maker can make a decision on her own• M-BLEAQ(Sinha, Malo, Deb, ECJ 2014)

Variation in Expectation(Sinha, Malo andDeb, 2016)• Optimistic PO front: No power on LL DM• Pessimistic PO front: Complete power on LL DM• Leader optimizes worst outcome from LL• The difference between
optimistic and pessimistic fronts
provide DM ideas at UL
Without LL decision-making

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Bilevel Optimization with Uncertainties
Ø

Uncertainty is, in most cases, inevitable in practical applications.

Ø

Sources of uncertainties:

ØIn the context of bilevel optimization problems

Ø

Ø

Ø

Imperfect implementation, changing environment, etc.

Ø

Uncertainty in design variables and parameters.

Ø

Uncertainty in objective and constraint function computations (Noise)ØUncertainty in decision making information.

Ø

Uncertainty in control of decision-making preferences between twolevels.

Robust Bilevel Optimization• Both upper and lower-level variables are uncertain within
their neighborhoods: Type-I Robustness:

Uncertainties in the context of bilevel optimization have NOT beenformally studied.
Clear mathematical definitions and formulations of robust/reliablebilevel solutions do NOT exist.
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Note that even if ∆y = 0, LL is uncertain due to ∆x perturbation,
stays as parameter uncertainties at LL
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

26

DSf

5 June 2017

Bilevel Optimization with
Uncertainties:
Big Picture

Robust Bi-Level
Optimization
Lower-level variables are uncertain
Global & Sensitivef(y)Local & Robust
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Robustness-based (Cont.)y
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Type-II Robustness

Feasible Region(0.6, 1.2)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

27

DSf

5 June 2017

IOWA Raccoon Watershed

IOWA Raccoon Watershed Results(GECCO-2017)

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Constrained Bilevel OptimizationØConstraints exist in almost every
practical engineering design
problem, and play a critical role indeciding the optimal solution.

Ø

The deterministic optimum usuallylies on a constraint surface or at theintersection of constraint surfaces.

ØMany studies aim to handle thisissue in single level optimization,none yet in the domain of bilevel
optimization.

ØFail to remain feasible in many occasions.

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Reliability in Bilevel Problem
Ø

Reliable bilevel solution definition:ØP () signify the joint probability of the solution (x, y) being feasible for all
constraints.

Ø

The effect of uncertainties in lower, upper or both levels are different
because of the unequal importance of each level.

ØTest problems proposed for the purpose of concept demonstration, NOT for
algorithm performance assessment.
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

28

DSf

5 June 2017

A Scenario
Ø

Tri-Level Optimization

Constraint functions at both levels
Lower Level

Feasible Region• Three levels of optimization problems interlinked by twoconsecutive levels• Min 𝓕(x,y,z)• Min F(y,z), given x• Min f(z), given x and y• Constraints are expected at every level• To make an application realistic, we need to replace lowest
level heuristic/rule based• Not much work available, but all issues discussed before
are applicable here too
Feasible Region
Upper Level

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb• BLEAQ can be extended• Currently pursuing

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

A Case Study: Supply Chain Management
YearlyStrategic Level
Transport Cost

State-Level and Zip-Level Results
44,000 ZIP Codes

Operational Level
Transport Cost

Weekly• UL: Plant to destination
layput• LL: At each plant, carriercompanies are predetermined• Allocation of goods to carrier
is LL task
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

Advantage of Using Bilevel Optimization Over
Single-Level Optimization:

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

29

DSf

5 June 2017

Uncertainty in Demand

Bi-Objective at Operational Level

Seasonal demand of goods assumed with uncertainty
Robust bi-level optimization performed
Robust solution is able to handle uncertainties better thanthe deterministic solution

Operational level at each plant considers two objectives:
Transport costService quality obtained carrier companies:

Produces a PO front at each plant
Strategic level chooses the best overall Transport Cost

Trade-off:

At one of the plants

Average service quality over all plants

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Conclusions

Tri-Level Consideration
Yearly, Plant todestination layout
Quarterly, Choice ofCarriers
Daily, Allocation of
goods to trucks

Advantage of Using Tri-level Optimization:

Finer optimization

CEC-2017, San Sebastian, Spain

Most benefit
Ankur Sinha and Kalyanmoy Deb

sfdsFDSA

CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

Bilevel problems are plenty in practice, but are avoided
due to lack of efficient methods
Bilevel optimization received lukewarm interest by EA
researchers so far
Population approach of EA makes tremendous potential
Nested nature of the problem makes the task
computationally expensive
Meta-modeling based EBO and its extensions showpromiseExtension to Tri-Level optimization is needed
Application to industry would be beneficial
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

30

DSf

5 June 2017

Some References
J.F. Bard. Practical bilevel optimization: Algorithms and applications. The Netherlands: Kluwer, 1998.

Ø

L. Brotcorne, M. Labbé, P. Marcotte, and G. Savard. A Bilevel Model for Toll Optimization on a
Multicommodity Transportation Network, Transportation Science, pages 345-358, 35(4), 2001.

Ø

S. Dempe. Foundations of bilevel programming. Kluwer, Dordrecht, 2002.

Ø

S. Dempe, J. Dutta, and B.S. Mordukhovich (2007). New necessary optimality conditions in optimistic
bilevel programming. Optimization, 56(5-6), 577–604.

Ø

J. Fliege, and L.N. Vicente (2006). Multicriteria approach to bilevel optimization. Journal of Optimization
Theory and Applications, 131(2), 209–225.

Ø

A. Sinha, P. Malo, and K. Deb. Efficient evolutionary algorithm for single-objective bilevel optimization.
CoRR, abs/1303.3901, 2013.

Ø

A. Sinha, P. Malo and K. Deb. An improved bilevel evolutionary algorithm based on quadratic
approximations. In 2014 IEEE Congress on Evolutionary Computation (CEC-2014). IEEE Press, 2014.

Zhichao Lu, PhD StudentØ

Y. Wang, Y. C. Jiao, and H. Li. An evolutionary algorithm for solving nonlinear bilevel programming
based on a new constraint-handling scheme. IEEE Transaction on Systems, Man and Cybernetics Part
C: Applications and Reviews, pages 221–232, 32(2), 2005.

Michigan State University
East Lansing, MI 48864, USAØYuping Wang, Hong Li, and Chuangyin Dang. A new evolutionary algorithm for a class of nonlinear
bilevel programming problems and its global convergence. INFORMS Journal on Computing,23(4):618–629, 2011.
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

sfdsFDSAOther Main Collaborators

Ø

Dr. Pekka Malo
Department of Information and Service Economy
Aalto University School of Business, Finland
Email: pekka.malo@aalto.fi

Electrical and Computer Engineering

kdeb@egr.msu.edu

Source:www.bilevel.org
CEC-2017, San Sebastian, Spain
Ankur Sinha and Kalyanmoy Deb

31