Created by Neevia Document Converter trial version http://www.neevia.
com
Created by Neevia Document Converter trial version
Chris Fricke Department of Mathematics and Statistics University of Melbourne
An Introduction to Bilevel Programming
Created by Neevia Document Converter trial version http://www.neevia.com
Outline
What is Bilevel Programming? Origins of Bilevel Programming. Some Properties of Bilevel Programs. The Linear Bilevel Programming Problem. Applications. References.
Created by Neevia Document Converter trial version http://www.neevia.com
What is Bilevel Programming?
Created by Neevia Document Converter trial version http://www.neevia.com
What is Bilevel Programming?
A mathematical program that contains an optimization problem in the constraints. * Evolved in two ways:
A logical extension of mathematical programming. Generalisation of a particular problem in game theory (Stackelberg Game).
*Bracken and McGill, Operations Research, Vol. 21 (1973)
Created by Neevia Document Converter trial version http://www.neevia.com
General Bilevel Programming Problem (Bard, 1998)
min F(x, y)
xX
s.t.
G(x, y) 0
min f(x, y)
y Y
s.t.
g(x, y) 0 x, y 0
Created by Neevia Document Converter trial version http://www.neevia.com
Origins of Bilevel Programming
Game Theory Approach Mathematical Programming Approach
Created by Neevia Document Converter trial version http://www.neevia.com
Origins of Bilevel Programming
Stackelberg
(The Theory of the Market Economy, Oxford University Press, 1952).
Bracken and McGill
("Mathematical Programs with Optimization Problems in the Constraints", Operations Research Vol. 21 No. 1, 1973).
Created by Neevia Document Converter trial version http://www.neevia.com
Game Theory Approach
Created by Neevia Document Converter trial version http://www.neevia.com
Elementary Game Theory
Situations involving more than one decision maker (player). Leads to the notion of conflict or competition. Each player has a number of available strategies with corresponding payoffs. Simplest case: Two-person, zero-sum game.
Created by Neevia Document Converter trial version http://www.neevia.com
Two-person Zero-sum Game: Assumptions
One player's gain = other player's loss. Players make decisions simultaneously. Players have perfect information
Of both their own and their opponent's permissible strategies and corresponding payoff.
Players do not cooperate.
Created by Neevia Document Converter trial version http://www.neevia.com
Two-person Zero-sum Game
Payoff matrix:
Player II
a1
Player I
A1 A2 v11 v12
...
a2 v21 v22 . . . . . . . . . am vm1 vm2
An . . . v1n . . . v2n . . . . . . vmn
Created by Neevia Document Converter trial version http://www.neevia.com
Stackelberg Game: Assumptions
One player's gain = the other player's loss. Players make decisions in specified order. Second player reacts rationally to first player's decision. Players have perfect information
Of both their own and their opponent's permissible strategies and consequent payoff.
Players do not cooperate.
Created by Neevia Document Converter trial version http://www.neevia.com
Stackelberg Game
Payoff matrix: (Bimatrix Game)
a1
A1 (v11, w 11) A2 (v12, w 12)
...
An . . . (v1n, w 1n)
a2 (v21, w 21) (v22, w 22) . . . (v2n, w 2n) . . . . . . . . . . . . am (vm1, w m1) (vm2, w m2) . . . (vmn, w mn)
Player I Payoff Player II Payoff
Created by Neevia Document Converter trial version http://www.neevia.com
Stackelberg Game: Definitions
Player who moves first is called the LEADER. Player who reacts (rationally) to the leader's decision (strategy) is called the FOLLOWER. The actions of one affect the choices and payoffs available to the other, and viceversa.
Created by Neevia Document Converter trial version http://www.neevia.com
Stackelberg Game: Solution Methods
Small instances can be solved analytically (standard game theory techniques e.g. graphical method). How to analyze/solve when each player has many available strategies? How to incorporate a complex relationship between the strategies and payoffs?
Created by Neevia Document Converter trial version http://www.neevia.com
Extension to Bilevel Programming
Also allows additional constraints to be placed on the player's strategies. Mathematical programming viewpoint:
LEADER moves first and attempts to minimize their own objective function. FOLLOWER observes the leader's action and moves in a way that is personally optimal.
Created by Neevia Document Converter trial version http://www.neevia.com
Mathematical Programming Approach
Some Distinctions
General mathematical program:
min f(x)
Created by Neevia Document Converter trial version http://www.neevia.com
s.t.
Ax b
x0
Created by Neevia Document Converter trial version http://www.neevia.com
Some Distinctions
Multiple objective program:
min f(x)
x
min g(x)
x
s.t.
Ax b
x0
Created by Neevia Document Converter trial version http://www.neevia.com
Some Distinctions
Bilevel program:
min f(x, y)
x
s.t.
A(x, y) b
min g(x, y)
y
s.t.
C(x, y) d x, y 0
Created by Neevia Document Converter trial version http://www.neevia.com
General Bilevel Programming Problem (BLPP)
min F(x, y)
xX
s.t.
G(x, y) 0
min f(x, y)
y Y
s.t.
g(x, y) 0 x, y 0
Properties of Bilevel Programs
Created by Neevia Document Converter trial version http://www.neevia.com
Existence of Solutions Order of Play
Created by Neevia Document Converter trial version http://www.neevia.com
Existence of Solutions
A BLPP need not have a solution. Restricting the functions F, G, f, g to be continuous and bounded DOES NOT guarantee the existence of a solution.
Created by Neevia Document Converter trial version http://www.neevia.com
Example (Bard, 1998)
Created by Neevia Document Converter trial version http://www.neevia.com
Example 1
to the followers problem as The solution y a function of x is:
Created by Neevia Document Converter trial version http://www.neevia.com
Substituting these values into the leaders problem gives:
Example 1
Solution space for leaders problem:
Example 1
Created by Neevia Document Converter trial version http://www.neevia.com
1/4
1/2
3/4
x1
Created by Neevia Document Converter trial version http://www.neevia.com
Example 1
Leaders optimal solution:
F 4
F = 1.5 3 x = (1 , 4 4) y = (0, 1)
1/4
1/2
3/4
x1
Created by Neevia Document Converter trial version http://www.neevia.com
Example 1
3 , At x = (1 4 4) followers optimal solution is f = 1 at any point on the line y 1 + y 2 = 1 Corresponding solution for leader is
F = 2y 1 + 3 2
F [1.5, 3.5]
No way for the leader to guarantee they achieve their minimum payoff No solution.
Created by Neevia Document Converter trial version http://www.neevia.com
Order of Play
The order in which decisions are made is important. The roles of leader and follower are NOT interchangeable (problem is not symmetric).
Created by Neevia Document Converter trial version http://www.neevia.com
Reverse the previous example:
Example 2
Created by Neevia Document Converter trial version http://www.neevia.com
Example 2
to the followers problem as The solution x a function of y is:
Created by Neevia Document Converter trial version http://www.neevia.com
Substituting these values into the leaders problem gives:
Example 2
Solution space for leaders problem:
Example 2
1/4 1/2 3/4
y1
-1
-2
-3 0
Created by Neevia Document Converter trial version http://www.neevia.com
Created by Neevia Document Converter trial version http://www.neevia.com
Example 2
Solution space for leaders problem:
0 1/4 1/2 3/4 1 y1
-1
-2
Optimal solution
-3
1 , y = (1 2 2) f = 2.5
Created by Neevia Document Converter trial version http://www.neevia.com
Example 2
= (1 1) y At 2, 2 followers optimal solution is F = 2.5 at any point on the line x1 + x2 = 1
Comparison of solutions:
Created by Neevia Document Converter trial version http://www.neevia.com
The Linear Bilevel Programming Problem (LBLPP)
Created by Neevia Document Converter trial version http://www.neevia.com
General Bilevel Programming Problem (Bard, 1998)
min F(x, y)
xX
s.t.
G(x, y) 0
min f(x, y)
y Y
s.t.
g(x, y) 0 x, y 0
Created by Neevia Document Converter trial version http://www.neevia.com
General LBLPP
min F(x, y) = c1x + d 1y
xX
s.t.
A1x + B1y b1
min f(x, y) = c2x + d 2y
y Y
s.t.
A2x + B2y b2
Created by Neevia Document Converter trial version http://www.neevia.com
Definitions
Constraint region of the BLPP:
S = {(x, y) : x X, y Y, A1x + B1y b1, A2x + B2y b2}
Followers feasible set for each fixed x X :
S(x) = {y Y : B2y b2 A2x}
Followers rational reaction set:
S(x)]} P(x) = {y Y : y argmin[f(x, y) : y
Created by Neevia Document Converter trial version http://www.neevia.com
Definitions
Inducible Region:
IR = {(x, y) S, y P(x)}
When S and P(x) are non-empty, the BLPP can be written as:
min{F(x, y) : (x, y) IR}
Created by Neevia Document Converter trial version http://www.neevia.com
Example (Bard, 1998)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
(3, 6)
4 S
(4, 4)
(1,2) Inducible Region
(2, 1)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
(3, 6)
4 S
(4, 4)
(1,2) Inducible Region
Non-convex in general
(2, 1)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
(3, 6)
Optimal solution
4 S (4, 4)
(1,2) Inducible Region
x = 4 y = 4 F = 12 f = 4
(2, 1)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
x=3 F = 19
(3, 6)
4 S
(4, 4)
(1,2) Inducible Region
(2, 1)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
x=3 F = 19
(3, 6)
4 S
(4, 4)
y = 2.5 f = 2.5 F(3, 2.5) = 7
(1,2) Inducible Region
(2, 1)
Created by Neevia Document Converter trial version http://www.neevia.com
Pareto Optimality
Multiple objective problem. Feasible solution B dominates feasible solution A:
B at least as good as A w.r.t. every objective, B strictly better than A w.r.t. at least one objective.
Pareto optimal solutions:
Set of all non-dominated feasible solutions.
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
(3, 6)
Optimal solution
4 S (4, 4)
(1,2) Inducible Region
x = 4 y = 4 F = 12 f = 4
(2, 1)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
(3, 6)
4 S
(4, 4)
x=3 y=4
F = 13 f=4
(1,2) Inducible Region
(2, 1)
F(x, y) = x 4y f(y) = y
y
Created by Neevia Document Converter trial version http://www.neevia.com
(3, 6)
5 S -F 4 (4, 4) -f
Region of solutions dominant to (4,4)
(1,2) Inducible Region
(2, 1)
Created by Neevia Document Converter trial version http://www.neevia.com
Summary of Properties of Bilevel Programs
No guarantee of solution. Order in which decisions are made is important. No guarantee of Pareto optimality. Non-convex optimization problem. All of the above can apply even when all functions are continuous and bounded.
Created by Neevia Document Converter trial version http://www.neevia.com
Solution Methods for the LBLPP
Vertex Enumeration Penalty Methods KKT Conditions
Created by Neevia Document Converter trial version http://www.neevia.com
Represent the IR as a Piecewise Linear Function*
Theorem 1:
The IR can be written equivalently as a piecewise linear equality constraint comprised of supporting hyperplanes of S.
Theorem 2:
) ( x , y of the LBLPP occurs at a The solution vertex of S.
*Bard, Practical Bilevel Optimization, (1998)
Created by Neevia Document Converter trial version http://www.neevia.com
Solution Methods
These Theorems are exploited in vertex enumeration algorithm of Candler and Townsley*. Approach based on Simplex method. Various penalty methods also developed. Most common approach via use of KKT conditions.
*Candler and Townsley, Computers and Operations Research, Vol. 9 (1982)
Created by Neevia Document Converter trial version http://www.neevia.com
Karush-Kuhn-Tucker Conditions
the KKT conditions for a local Given x = x y optimum at the point for
are:
Created by Neevia Document Converter trial version http://www.neevia.com
Replace the Followers Problem with its KKT Conditions
Recall the followers problem:
Created by Neevia Document Converter trial version http://www.neevia.com
KKT Conditions
Let u and v be the dual variables associated with the two sets of constraints.
Created by Neevia Document Converter trial version http://www.neevia.com
KKT Conditions
Applying the KKT conditions to the followers problem gives:
Reformulation
Solve for x, y, u, v
Created by Neevia Document Converter trial version http://www.neevia.com
Created by Neevia Document Converter trial version http://www.neevia.com
Reformulation
Complementarity condition is non-linear.
Requires implementation of non-linear programming methods. Problem is further complicated if IR is not convex.
Created by Neevia Document Converter trial version http://www.neevia.com
Integer Programming Approach to Dealing with Non-Linearity
Write all inequalities in followers problem in the form:
gi(x, y) 0
Complementary slackness gives:
ui gi(x, y) = 0 Introduce binary variables z i {0, 1} and sufficiently large constant M
Created by Neevia Document Converter trial version http://www.neevia.com
Integer Programming Approach to Dealing with Non-Linearity*
Replace complementary slackness with the following inequalities:
ui Mz i, gi M(1 z i)
Now have a mixed-integer linear program Apply standard IP solvers (e.g. CPLEX). Drawback: increased number of variables and constraints Computational inefficiency.
*Fortuny-Amat and McCarl, Journal of the Operational Research Society, Vol. 32 (1981)
Created by Neevia Document Converter trial version http://www.neevia.com
Alternative Approach to Dealing with Non-Linearity
Rewrite complementary slackness term as sum of piecewise linear separable functions. Use globally convergent non-linear code to obtain solutions. Basis for Bard-Moore (branch-and-bound) algorithm for solving the LBLPP*
ui gi(x, y) = 0
i
*Bard and Moore, SIAM Journal of Scientific and Statistical Computing, Vol. 11 (1990)
ui gi(x, y) = 0
i
Created by Neevia Document Converter trial version http://www.neevia.com
min{ui, gi} = 0 (min{0, (gi ui)} + ui) = 0
i
Replace gi ui with new variables w i to give equivalent set of constraints:
Piecewise linear separable term Linear equalities
(min{0, w i} + ui) = 0
i
w i gi + ui = 0
Created by Neevia Document Converter trial version http://www.neevia.com
Applications
Economics Resource Allocation Transportation Network Design
Created by Neevia Document Converter trial version http://www.neevia.com
Applications
Multilevel systems
A high level decision maker is able to influence the decisions made at lower levels, without having complete control over their actions. Objective function of one department is determined, in part, by variables controlled by other departments operating at higher or lower levels.
Created by Neevia Document Converter trial version http://www.neevia.com
Economic Planning at the Regional or National Level
Leader: Government
Controls policy variables e.g. tax rates, import quotas. Maximize employment / Minimize use of a resource.
Follower:
Industry to be regulated
Maximize net income s.t. economic and governmental constraints.
Created by Neevia Document Converter trial version http://www.neevia.com
Determining Price Support Levels for Biofuel Crops
Leader: Government
Determine the level of tax credits for each biofuel product. Minimize total outlays.
Follower:
Petro-chemical industry
Minimize costs.
Created by Neevia Document Converter trial version http://www.neevia.com
Resource Allocation in a Decentralized Firm
Leader: Central resource supplier
Allocates products to manufacturers. Maximize profit of firm as a whole.
Follower: Manufacturing facilities at different locations
Determines own production mix/output. Maximize performance of own unit.
Created by Neevia Document Converter trial version http://www.neevia.com
Transportation System Network Design
Leader: Central planner
Controls investment costs e.g. which links to improve. Influence users preferences to minimize total costs.
Follower:
Individual users
Their route selection determines the traffic flows and therefore operational costs. Seek to minimize cost of own route.
Created by Neevia Document Converter trial version http://www.neevia.com
Summary of Bilevel Programming Problems
min F(x, y)
xX
s.t.
G(x, y) 0
min f(x, y)
y Y
s.t.
g(x, y) 0 x, y 0
Created by Neevia Document Converter trial version http://www.neevia.com
Summary of Bilevel Programming Problems
No guarantee of solution. Order in which decisions are made is important. No guarantee of Pareto optimality. Non-convex optimization problem. In linear case, a number of possible reformulations exist to aid solution. Used for specific applications.
Created by Neevia Document Converter trial version http://www.neevia.com
References
Bard, J.F. Practical Bilevel Optimization: Applications and Algorithms, Kluwer Academic Press, 1998. Shimizu, K., Ishizuka, Y. and Bard, J.F., Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic Publishers, 1997. http://www.acsu.buffalo.edu/~bialas/
