Pessimistic Bilevel Optimization: A Survey

June Liu; Yuxin Fan; Zhong Chen; Yue Zheng

doi:10.2991/ijcis.11.1.56

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 11, Issue 1, 2018, Pages 725 - 736

Pessimistic Bilevel Optimization: A Survey

Authors

June Liu¹^,xun4025@126.com, Yuxin Fan²^,fann.song@yahoo.com, Zhong Chen³^{, *}^,chenzhtong@yangtzeu.edu.cn, Yue Zheng¹^{, †}^,zhengyuestone@126.com

¹School of Management, Huaibei Normal University, Huaibei 235000, Anhui, P.R. China

²Huazhong University of Science and Technology, Wuhan 430074, P.R. China

³School of Information and Mathematics, Yangtze University, Jingzhou 434023, Hubei, P.R. China

^*Corresponding author.

^†Corresponding author.

Corresponding Authors

Zhong Chenchenzhtong@yangtzeu.edu.cn, Yue Zhengzhengyuestone@126.com

Received 5 January 2018, Accepted 22 February 2018, Available Online 9 March 2018.

DOI: 10.2991/ijcis.11.1.56 How to use a DOI?
Keywords: Bilevel optimization; Pessimistic formulation; Stackelberg games
Abstract: Bilevel optimization are often addressed in an organizational hierarchy in which the upper level decision maker is the leader and the lower level decision maker is the follower. The leader frequently cannot obtain complete information from the follower. As a result, the leader most tends to be risk-averse, and then would like to create a safety margin to bound the damage resulting from the undesirable selection of the follower. Pessimistic bilevel optimization represents an attractive tool to model risk-averse hierarchy problems, and would provide strong ability of analysis for the risk-averse leader. Since to the best of our knowledge, there is not a comprehensive review on pessimistic bilevel optimization, the goal of this paper is to provide a extensive review on pessimistic bilevel optimization from basic definitions and properties to solution approaches. Some real applications are also proposed. This survey will directly support researchers in understanding theoretical research results, designing solution algorithms and applications in relation to pessimistic bilevel optimization.
Copyright: © 2018, the Authors. Published by Atlantis Press.
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Bilevel decision-making problems^10,18,38,49, motivated by Stackelberg game theory⁴², are hierarchical optimization problems in which their constraints are defined in part by another parametric optimization problem. The decision makers at the upper level and the lower level are respectively termed as the leader and the follower, and make their individual decisions in sequence with the aim of optimizing their respective objectives. As is well-known, bilevel optimization plays an exceedingly important role in different application fields, such as transportation, economics, ecology, engineering and others¹⁹. However, solving such a problem is not an easy task. Even if a linear bilevel programming problem is generally difficult to solve, and was proved to be strongly NP-hard²².

In general, a bilevel programming problem can be stated as:

(1)minx,y''F''(x,y)s.t G(x)≤0,y∈Ψ(x),

where Ψ(x) is the set of solutions to the lower level problem

(2)minyf(x,y)s.t. g(x,y)≤0,

Here x ∈ Rⁿ and y ∈ R^m.

It is worthwhile noting that the lower level problem may have multiple solutions for every (or some) fixed value of the upper level decision making variable. If the solution of the lower level problem is not unique, it is difficult for the leader to predict which point in Ψ(x) the follower will choose. As a result, it is difficult to determine the leader’s solution. That is the reason why we use the quotation marks in problems (1)–(2). To overcome this situation, the majority of authors used optimistic formulation and pessimistic formulation, which represented the two extreme situations between the leader and the follower. In the optimistic formulation (e.g., see Ref. 18 and the references therein), the follower always selects a strategy in Ψ(x) that suits the leader best. It is formulated as:

(3)minx,yF(x,y)s.t. x∈X, y∈Ψ(x),

where X := {x : G(x) ⩽ 0}.

Alternatively, pessimistic formulation (e.g., see Ref. 18 and the references therein) refers to the case where the leader protects himself against the worst possible situation, and can be written as:

(4)minx∈Xmaxy∈Ψ(x)F(x,y).

Note that there are several survey papers on bilevel/multilevel programming/decision-making in the past 20 years. However, these survey focus on an optimistic bilevel optimization. For example, Ben-Ayed¹¹, Wen and Hsu⁴⁵ presented the basic models, solution definitions, solution approaches and applications of the optimistic linear bilevel optimization. Colson et al.^15,16, Vicente and Calamai⁴⁴ focused on traditional solution concepts and solution approaches for the optimistic bilevel programming problems. Dempe¹⁹ summarized the main research directions and the main fields of applications of bilevel programming, but mainly fixed attention on the optimistic formulation. Sakawa and Nishizaki³⁹ reviewed interactive fuzzy programming approaches for the optimistic bilevel/multilevel programming problems which focus on cooperative decision-making in decentralised organizations. Kalashnikov et al.²³ presented a survey of bilevel programming and application area. Zhang, Han and Lu⁵⁰ reviewed the fuzzy bilevel decision-making techniques which includes models, approaches and systems. Lu, Shi and Zhang³² identified nine different kinds of relationships amongst followers by establishing a general framework for bilevel multifollower decision problems. Furthermore, Lu et al.³³ analyzed various kinds of relationships between decision entities in a multifollower trilevel (MFTL) decision problem, and then proposed an MFTL decision making framework, in which 64 standard MFTL decision situations and their possible combinations are identified. Recently, Lu et al.³⁴ developed the latest research on multilevel decision-making involving theoretical research results and applications. Sinha, Malo and Deb⁴⁰ presented an introduction to progress made by evolutionary computation towards handing bilevel optimization. Sinha, Malo and Deb⁴¹ developed a comprehensive review on bilevel optimization from classical to evolutionary approaches, and then discussed a number of potential application problems. The above survey papers have provided good references on optimistic bilevel optimization for researchers. Unfortunately, little is reviewed regarding the pessimistic bilevel optimization. Therefore, the authors in this paper will systematically review up-to-date pessimistic bilevel optimization which focuses on properties, solution approaches and applications.

To conduct this literature review, there are two main types of article being reviewed in this survey: Type I - articles on solution definitions and properties (including optimality conditions, existence of solutions and complexity) and Type II - articles on solution approaches. The search and selection of these articles were performed according the four steps as follows:

Step 1. Publication database identification and determination. Publication databases, such as Science Direct, SpringerLink, IEEE Xplore, Taylor & Francis and Google scholar, were selected to provide a comprehensive bibliography of papers on pessimistic bilevel optimization.
Step 2. Preliminary screening of articles. The search was first performed based on related keywords of pessimistic bilevel optimization. The articles were then selected as references if they satisfied one of the following criteria that they 1) present pessimistic bilevel optimization model; 2) propose solution concepts and approaches for pessimistic bilevel optimization; 3) provide a real-world pessimistic bilevel application.
Step 3. Result filtering for Type 1 articles. Based on the keywords of the preliminary references related to pessimistic bilevel optimization, these papers were divided into four groups: solution definitions, optimality conditions, existence of solutions and complexity, which are mainly used in Sections 2 and 3.
Step 4. Type 2 article selection. Based on the keywords of solution approaches to pessimistic bilevel optimization, these papers were divided into four groups: penalty methods, Kth-Best algorithm, approximation approach and reduction method, which are mainly used in Section 4.

In this paper, we focus on pessimistic bilevel optimization, and aim at answering some research questions as follows:

RQ1 What are the definitions and properties of pessimistic bilevel optimization?
RQ2 What are the state-of-the-art solution approaches to solve pessimistic bilevel optimization?
RQ3 What are the main applications of pessimistic bilevel optimization?

The main contributions of this paper are:

1)
Review of definitions of pessimistic bilevel optimization and related properties, such as optimality conditions, existence of solutions and complexity.
2)
Review and classification of solution approaches to pessimistic bilevel optimization.
3)
Future directions are suggested in the area of pessimistic bilevel optimization.

The remainder of this paper is organized as follows. In Sections 2 and 3, we review definitions and properties of pessimistic bilevel optimization and answer RQ1. Section 4 describes solution approaches to pessimistic bilevel optimization and answer RQ2. We answer RQ3 in Section 5 which is dedicated to the applications. Finally, we conclude this paper and provide some future directions in Section 6.

2. Definitions of pessimistic bilevel optimization

To understand and analyze solution approaches and application developments of pessimistic bilevel optimization, this section reviews the notations and definitions.

2.1. Definitions

In this subsection, some important definitions of pessimistic bilevel optimization are itemized below.

Definition 2.1

(a)
Constraint region of problem (4):
S:={(x,y):G(x)≤0,g(x,y)≤0}.
(b)
Projection of S onto the leader’s decision space:
S(X):={x∈X:∃y,such that (x,y)∈S}.
(c)
Feasible set for the follower ∀x ∈ S(X):
Y(x):={y:g(x,y)≤0}.
(d)
The follower’s rational reaction set for x ∈ S(X):
Ψ(x):={y:y∈arg min[f(x,y):y∈Y(x)]}.
(e)
Inducible region or feasible region of the leader:
IR:={(x,y):(x,y)∈S,y∈Ψ(x)}.

To introduce the concept of a solution to problem (4) (also called pessimistic solution), one usually employs the following value function φ(x):

ϕ(x):=supy∈Ψ(x)F(x,y).

Definition 2.2

A pair (x^*, y^*) ∈ IR is called a solution to problem (4), if

ϕ(x*)=F(x*,y*),ϕ(x*)≤ϕ(x),∀(x,y)∈IR.

When the feasible set of the follower does not depend on the upper level decision variables, i.e., g(x, y) in problem (2) is reduced to g(y), problem (4) is referred as an independent pessimistic bilevel problem⁴⁶. Note that it is also called weak Stackelgerg problem in Ref. 30. Mention that many studies, in particular, the existence of solutions have been devoted to the weak Stackelgerg problem. In the following, some definitions concerning, in particular, approximate solutions (ɛ-Stackelberg solution, ɛ-Stackelberg equilibrium pair) to the weak Stackelgerg problem will be described.

Definition 2.3

(Loridan and Morgan²⁷) Any point x^* verifying v₁ = φ (x^*) is called a Stackelberg solution to the weak Stackelberg problem. Here, v1: =infx∈Xϕ(x) .

Definition 2.4

(Loridan and Morgan²⁷) A pair (x^*, y^*) verifying v₁ = φ(x^*) and y^* ∈ Ψ(x^*) is called a Stackelberg equilibrium pair.

Definition 2.5

(Loridan and Morgan²⁷) Let ɛ > 0 be a given number. A point x^*is an ɛ-Stackelberg solution if and only if x^* ∈ X and φ(x^*) ≼ v₁ + ɛ.

Definition 2.6

(Loridan and Morgan²⁷) A pair (x^*, y^*) is an ɛ-Stackelberg equilibrium pair if and only if x^*is an ɛ-Stackelberg solution and y^* ∈ Ψ(x^*).

In addition to the above definitions of pessimistic bilevel optimization, Alves and Antunes⁸ presented and illustrated a definition of pessimistic solution of semivectorial bilevel problem, and made comparison of optimistic solution, pessimistic solution, deceiving solution and rewarding solution.

3. Properties of pessimistic bilevel optimization

According to the definitions in Section 2, we categorize the various properties of pessimistic bilevel optimization, and then list some of the well-known properties.

3.1. Existence of solutions

As is well-known, the study of existence of solutions for pessimistic bilevel optimization is a difficult task. An initial step in this direction was developed by Lucchetti, Mignanego and Pieri³⁵ who proposed some examples that fail to have a solution. Mention that the most studies have been devoted to the weak Stackelgerg problem. Aboussoror and Loridan², Aboussoror³ have given sufficient conditions to obtain the existence of solutions to the weak Stackelgerg problem via a regularized scheme. Any accumulation point of a sequence of regularized solutions is a solution to the weak Stackelgerg problem. Aboussoror and Mansouri⁵ have deduced the existence of solutions to the weak Stackelgerg problem via d.c. problems. Similar results using reverse convex and convex maximization problems are given in Aboussoror, Adly and Jalby⁶. Loridan and Morgan²⁷ have obtained some results for approximate solutions of the weak Stackelgerg problem by using a theoretical approximation scheme. Any accumulation point of a sequence of ɛ-approximate solutions of the approximation problems is an ɛ -approximate solution to the weak Stackelgerg problem. The interested reader can refer to the references about the approximate solutions of the weak Stackelgerg problem. Furthermore, Loridan and Morgan²⁸ improved and extended some properties proposed in Ref. 27. Similar results using approximation scheme were given in Ref. 29. Lignola and Morgan²⁴ discussed a more general weak Stackelberg formulation in which the follower’s rational reaction set Ψ(x) is replaced by a parameterized constraint Ψ(t, x) (t is a parameter). Marhfour³⁷ have established existence and stability results for ɛ-mixed solutions of weak Stackelberg problems. In particular, the results are given under general assumptions of minimal character without any convexity assumption.

For the linear pessimistic bilevel problems, using the strong dual theorem of linear programming and penalty method, Aboussoror and Mansouri⁴ have established the existence results of solutions. Note that, the strong-weak Stackelberg problems have been reduced the weak Stackelgerg problem under some conditions. Aboussoror and Loridan¹ have studied the existence of solutions of strong-weak Stackelberg problems. In particular, using the regularization and the notion of variational convergence, Aboussoror⁷ have given sufficient conditions to ensure the existence of solutions to such problems. The obtained results in Refs. 1 and 7 can be applied to the weak Stackelgerg problem by deleting some variables.

When the pessimistic bilevel optimization problem (4) does not have a solution, which may arise even under strong assumptions, the leader can make do with alternative solution concepts. Based on this, Lignola and Morgan²⁵ recently have considered a concept of viscosity solution which can obviate the lack of optimal solutions. In particular, they have given sufficient conditions using regularization families of the solutions map to the lower level problem, ensuring the existence of the corresponding viscosity solutions.

3.2. Optimality conditions

The optimality conditions for pessimistic bilevel optimization and pessimistic semivectorial bilevel optimization have been proposed in the literature. A first attempt was made by Dassanayaka¹⁷ using implicit programming approach, minmax programming approach and duality programming approach respectively. Using the advanced tools of variational analysis and generalized differentiation, Dempe²⁰ derived several types of necessary optimality conditions via the lower-level value function approach and the Karush-Kuhn-Tucker (KKT) representation of lower-level optimal solution maps. Furthermore, the upper subdifferential necessary optimality conditions are obtained, and the links are also established between the necessary optimality conditions of the pessimistic and optimistic versions in bilevel programming. Liu et al.²⁶ discussed a class of pessimistic semivectorial bilevel optimization in which the lower level problem was a multiobjective optimization problem, and presented the first order necessary optimality conditions of such a problem. These various necessary optimality conditions could be helpful to develop fast algorithms to obtain solutions of pessimistic bilevel optimization.

3.3. Complexity

The complexity of pessimistic bilevel optimization is easily confirmed at its simplest version, i.e. linear pessimistic bilevel problem. Wiesemann et al.⁴⁶ discussed a class of linear dependent pessimistic bilevel problem in which the follower’s feasible set depends on the upper level decision variables as follows:

(5)minxc⊤xs.t. Ax+By ≥ b,∀y ∈Ψ(x), Ψ(x)=arg minz∈R+m{f⊤z:Cx+Dz ≥ w}, x∈R+n,

where c ∈ Rⁿ, A ∈ R^p×n, B ∈ R^p×m, b ∈ R^p, f ∈ R^m, C ∈ R^q×n, D ∈ R^q×mand w ∈ R^q. When the lower level problem satisfies C = 0, i.e. the follower’s feasible set does not depend on the upper level decision variables, problem (5) can be called a linear independent pessimistic bilevel problem.

Under the certain assumptions, Wiesemann et al.⁴⁶ illustrated that: 1) The independent linear pessimistic formulation of problem (5) can be solved in polynomial time; 2) If the number of the lower level decision variables is constant, the dependent linear pessimistic bilevel problem can be solved in polynomial time. Otherwise, it is strongly NP-hard.

4. Solution approaches of pessimistic bilevel optimization

4.1. Penalty methods for the linear case

At present, the proposed penalty methods^4,51 were only used to solve the linear pessimistic bilevel optimization problem. An initial step in this direction was developed by Aboussoror and Mansouri⁴. Using the strong dual theory of linear programming and penalty method, they transformed the linear pessimistic bilevel optimization problem:

(6)minx∈Xmaxy∈Ψ(x)c⊤x+d1⊤y

where Ψ(x) is the set of solutions to the lower level problem

(7)miny≥0d2⊤ys.t. By≤b−Ax

into a single-level optimization problem:

(8)minx,t,uc⊤x+d2⊤t+(b−Ax)⊤us.t.−B⊤u≤ kd2−d1, Bt≤ k(b−Ax), x∈X,t,u≥0,

where t ∈ R^m, u ∈ R^pand k > 0 is a penalty parameter.

Under some assumptions, Aboussoror and Mansouri ⁴ proved that there exists a k^*> 0 such that for all k > k^*, if (x_k, t_k, u_k) is a sequence of solutions of the problem (8), x_ksolves problems (6)–(7). Unfortunately, no numerical results were reported.

A more recent contribution by Zheng et al.⁵¹, follows the ideas of Aboussoror and Mansouri⁴, who presented a new variant of the penalty method to solve problems (6)–(7). Their method transformed it into the following penalty problem:

(9)minx,t,uc⊤x+kd2y+(b−Ax)⊤us.t.−B⊤u≤ kd2−d1, By≤b−Ax, x∈X,y,u≥0,

where u ∈ R^p, and k > 0 is a penalty parameter. The resulting algorithm involves the minimization of disjoint bilinear programming problem (9) for a fixed value of k. Two simple examples illustrate the proposed algorithm is feasible.

4.2. Modified Kth-Best algorithm for the linear case

An important property of the solution to the linear pessimistic bilevel optimization problems (6)–(7) is that there exists a solution which occurs at a vertex of the polyhedron W. Here W is the constraint region of problems (6)–(7), i.e.

W:={(x,y):x∈X,By≤ b−Ax,y ≥ 0}.

This property induces the possibility of developing algorithms which search amongst vertices of W in order to solve the linear pessimistic bilevel optimization problems.

Zheng, Fang and Wan⁵² first proposed a modified version of Kth-Best algorithm to the linear pessimistic bilevel optimization problem. After sorting all vertices in ascending order with respect to the value of the upper level objective function, this algorithm selects the first vertex to check if it satisfies the terminate condition, and the current vertex is a solution of problems (6)–(7) if it is yes. Otherwise, the next one will be selected and checked.

4.3. Approximation approach

To solve independent pessimistic bilevel problem, several authors (Loridan and Morgan³⁰; Tsoukalas, Wiesemann and Rustem⁴³; Wiesemann et al.⁴⁶) presented the approximation approaches. Loridan and Morgan³⁰ presented the following regularized problem:

(10)minx∈Xsupy∈Ψ(x,ɛ)F(x,y)

where ɛ > 0 and Ψ(x, ɛ) is the set of ɛ-solutions of the lower level problem

(11)minyf(x,y)s.t. y∈Y,

and the strong Stackelberg problem:

(11)minx∈Xinfy∈Ψ(x,β,γ)F(x,y)

where β, γ ⩾ 0 and Ψ(x, β, γ) is the set of γ-solutions of the parametrized problem

(13)minyg(x,y,β)s.t. y∈Y,

where g(x, y, β) = f(x, y) − βF(x, y) for any x ∈ X and y ∈ Y.

Based on the Molodtsov method, Loridan and Morgan³⁰ computed a sequence of solutions of strong Stackelberg problems (12)–(13) and investigated the relations with solutions to the independent pessimistic bilevel problem. Under some assumptions, they have been proved that a sequence of solutions of strong Stackelberg problem convergence to a lower Stackelberg equilibrium for the independent pessimistic bilevel problem.

On the other hand, Tsoukalas, Wiesemann and Rustem⁴³, Wiesemann et al.⁴⁶ considered the following independent pesssimistic bilevel optimization problem:

(14)minx∈Xf(x)s.t. g(x,y) ≤0,∀y∈argmaxy′∈Yh(x,y′).

To solve the independent pessimistic bilevel optimization problem (14), they presented an ɛ-approximation problem:

minx∈Xf(x)s.t. g(x,y) ≤0,∀y∈Yɛ(x),Yɛ(x)={z∈Y:h(x,z)<h(x,z′)+ɛ,∀z′∈Y},x∈X.

For a fixed value of ɛ, the above problem was reformulated as a single-level optimization problem:

minx,y,λf(x)s.t. λ(y)[h(x,z)−h(x,y)+ɛ] +(1−λ(y))g(x,y)≤0,∀y∈Y, x∈X,z∈Y,λ:Y→[0,1],

where the function λ : Y → [0,1] is a decision variable. Furthermore, they developed an iterative solution procedure for the ɛ-approximation problems. Numerical results illustrate the feasibility of the proposed ɛ-approximation method.

In particular, when the lower level corresponds to an equilibrium problem that is represented as a (parametric) variational inequality or, equivalently, a generalized equation, bilevel optimization problem can be called an MPEC (Mathematical Program with Equilibrium Constraints). C̆ervinka, Matonoha and Outrata¹⁴ proposed a new numerical method, which combines two types of existing codes, a code for derivative-free optimization under box constraints, and a method for solving special parametric MPECs from the interactive system, to compute approximate pessimistic solutions to MPECs.

4.4. Reduction method

Again, to solve problem (4), Zeng⁴⁸ presented its relaxation problem as follows:

(15)minx,y¯maxy∈Y˜(x,y¯)F(x,y)s.t. x∈X, g(x,y¯) ≤0, Y˜(x,y¯): ={y:g(x,y) ≤0,f(x,y) ≤f(x,y¯)}.

Proposition 3 in Ref. 48 means that if (x^*, y¯′ , y′) is a solution to problem (15), then there exists a point y^* ∈ Ψ(x^*) such that (x^*, y^*) solves problem (4). In other words, this result provides the reader with an important idea to compute the pessimistic bilevel optimization via investigating a regular optimistic bilevel programming problem.

For a pessimistic quadratic-linear bilevel optimization problem, Malyshev and Strekalovsky³⁶ reduced it to a series of optimistic bilevel optimization problems and then to the nonconvex optimization problems. Furthermore, they developed the global and local search algorithms.

In addition to the above several methods, Dempe, Luo and Franke²¹ proposed the global and local search algorithms for solving linear pessimistic bilevel optimization via the value method and the strong dual theory of linear programming. For the pessimistic bilevel mixed-integer programming problems, Lozano and Smith³¹ developed two methods (i.e. two-phase approach and cutting-plane algorithm) based on an optimal-value-function reformulation. Zheng, Zhuo and Chen⁵⁵ presented a maximum entropy approach to solve the pessimistic bilevel programming problems in which the set of solutions of the lower level problem is discrete. It should be noted that their approach need to obtain the set of solutions of the lower level problem in advance. This is not an easy work, but it may provide the reader with a new way to discuss the pessimistic bilevel optimization. Table 1 gives a comparison of the advantages and disadvantages of these algorithms.

Algorithm name	Advantages	Disadvantages
Penalty method⁴	Can find a solution via a sequence of bilinear programming.	Limited in pessimistic linear bilevel; Time-consuming for the large-scale problems.
Penalty method⁵¹	Can find a solution via a sequence of disjoint bilinear problems.	Limited in pessimistic linear bilevel; Time-consuming for the large-scale problems.
Kth-Best algorithm⁵²	Can find a global solution.	Limited in pessimistic linear bilevel; Time-consuming for the large-scale problems.
Global search algorithm²¹	Can find a global solution.	Limited in pessimistic linear bilevel; Algorithm works after enumeration of all different basic matrices;
Descent algorithm²¹	Can find a local optimal solution;	Limited in pessimistic linear bilevel; Time-consuming for the large-scale problems.
Approximation approach³⁰	Can find a solution via a sequence of optimistic bilevel.	Limited in independent pessimistic bilevel; Require a global solution at every update.
Approximation approach⁴⁶	Can find an ɛ-approximation solution.	Limited in independent pessimistic bilevel; Require a global solution at every update.
Reduction method³⁶	Can find a solution via a sequence of optimistic bilevel.	Limited in pessimistic quadratic-linear bilevel; Require a global solution at every update.
Reduction method⁴⁸	Can find a solution via an optimistic bilevel; Not require a global solution at every update.	Indirect method; The lack of a large number of numerical results to support.
Maximum entropy approach⁵⁵	Can find an ɛ-approximation solution.	Works after obtaining the solution set of the lower level problem; May be infeasible for the large-scale problems.

Table 1.

Advantages and disadvantages of the most relevant algorithms to solve pessimistic bilevel optimization.

5. Applications

Pessimistic bilevel optimization models have been applied to handle decentralized decision problems in the real world. In the following, we provide a small selection of actual or potential applications of pessimistic bilevel optimization in the literature.

Second best toll pricing

Second best toll pricing (SBTP) models determine optimal tolls of a subset of links in a transportation network by minimizing certain system objective, while the traffic flow pattern is assumed to follow user equilibrium (UE). As the UE problem may have multiple solutions under a given toll, the design objective will always worse off. To achieve more robust tolling, Ban et. al⁹ proposed a risk averse second best toll pricing approach aiming to optimize for the worst-case scenario which can be modeled as weak Stackelberg problem. In fact, it is an independent pessimistic bilevel optimization problem.

Production planning

Production-distribution (PD) planning problems are often addressed in an organizational hierarchy in which a distribution company that utilizes several depots is the leader and the manufacturing companies are the followers. The classical objective function of the leader is to minimize the total operating cost of the distribution company, and the followers optimize their respective production cost. However, the distribution company frequently cannot obtain complete production information from the manufacturing companies, and may thus become risk-averse. As a result, Zheng et al.⁵³ presented a risk-averse PD planning problem which is formulated as a pessimistic mixed-integer bilevel optimization model from the worst-case point of view. Other applications of pessimistic bilevel optimization to production planning can be found in Refs. 43 and 46.

Principal-agent problem

As is well-known, principal-agent problem is a classical problem in economics, in which a principal (the leader) sub-contracts a job to an agent (the follower). In real life, principal-agent relationships are commonly found in doctor-patient, employer-employee, corporate board-shareholders and politician-voters scenarios. Suppose that the agent prefers to act this job in his own interests rather than those of the principal. The principal is difficult to design a contract under incomplete and asymmetric information. As a result, design of such a contract appears as a pessimistic bilevel optimization problem. Studies that the readers can refer to are Ref. 43.

Interdiction game

Interdiction game covers important and diverse applications, such as critical infrastructure defense, stopping nuclear weapons projects, drug smuggling, marketing and attacker-defender problems. Its framework is a class of sequential decision-making problems in the context of max–min bilevel programming which in fact is a special case of pessimistic bilevel optimization. Some of the approaches that have acknowledged the max–min bilevel nature of this problem are Refs. 12, 13 and 47.

Venture investment

In a company making venture investments, all decision entities have individual objectives, constraints, and variables and do not cooperate with one another. The departments within the company are also in an uncooperative situation, but they need to use the same warehouse in this company. The CEO’s decision takes the responses of the selected departments into consideration and aims to maximize the company’s profit. Under incomplete and asymmetric information, the CEO cannot directly observe both departments’ effort and the inventory expense. As a result, the CEO would like to create a safety margin to bound the damage resulting from undesirable selections of the departments. Based on these, Zheng, Zhu and Yuan⁵⁴ developed a partially-shared linear pessimistic bilevel multi-follower programming problem, in which there is a partially-shared variable among the followers, to model the company making venture investments.

6. Conclusions and prospective research topics

Bilevel optimization problem plays an exceedingly important role in different application fields. Pessimistic formulation in bilevel optimization has become one of the major strategies for solving such problems in which the set of solutions of the lower level problem is not singleton. In this paper, we have addressed a survey of pessimistic bilevel optimization and answered our research questions.

RQ1 What are the definitions and properties of pessimistic bilevel optimization?

In Sections 2 and 3, we review of definitions of pessimistic bilevel optimization and related properties, such as optimality conditions, existence of solutions and complexity.
RQ2 What are the state-of-the-art solution approaches to solve pessimistic bilevel optimization?

In Section 4, we overviewed pessimistic bilevel solution approaches and provided four classifications of them. The first classification is based on penalty methods, while the second classification is Kth-Best Algorithm for the linear pessimistic bilevel optimization. The third classification is approximation approach to solve independent pessimistic bilevel optimization. The fourth classifies approaches depends on the reduction formulation of pessimistic bilevel optimization.
RQ3 What are the main applications of pessimistic bilevel optimization?

In Section 5, we indicated the applications of pessimistic bilevel optimization, such as second best toll pricing, production planing, principal-agent problem, interdiction game and venture investments.

This survey gives an overview on the state-of-the-art of pessimistic bilevel optimization. Based on the review, we can find that there are some directions that should be discussed for further research.

1)
The first order optimality conditions for pessimistic bilevel optimization is proposed, but it has not been organically combined with the algorithm. Furthermore, the higher order optimality conditions also should be studied. In addition, no systematic studies have been conducted on sensitivity analysis.
2)
Several existing methods can be used to solve linear pessimistic bilevel optimization and independent pessimistic bilevel optimization problems. It would be interesting to study a general pessimistic bilevel optimization which do not possess the independence property. In particular, it would be instructive to investigate how pessimistic bilevel optimization can be reduced to a single-level optimization problem and to discuss the relationship between them.
3)
The ultimate goal of pessimistic bilevel optimization is to provide strong ability of analysis and decision for the practical problems from the worst-case point of view. In particular, those problems often appear in highly complex and uncertainty environments. This requires further research on how intelligent algorithms can be applied to large-scale pessimistic bilevel optimization in the current age of big data.

Acknowledgments

The work presented in this paper was supported by the National Natural Science Foundation of China (11501233).

References

1.A Aboussoror and P Loridan, Strong-weak Stackelberg problems in finite dimensional spaces, Serdica Mathematical Journal, Vol. 21, 1995, pp. 151-170.

2.A Aboussoror and P Loridan, Existence of solutions to two-level optimization problems with nonunique lower-level solutions, Journal of Mathematical Analysis and Applications, Vol. 254, 2001, pp. 348-357.

3.A Aboussoror, Weak bilevel programming problems: existence of solutions, Advances in Mathematics Research, Vol. 1, 2002, pp. 83-92.

4.A Aboussoror and A Mansouri, Weak linear bilevel programming problems: existence of solutions via a penalty method, Journal of Mathematical Analysis and Applications, Vol. 304, 2005, pp. 399-408.

5.A Aboussoror and A Mansouri, Existence of solutions to weak nonlinear bilevel problems via MinSup and d.c. problems, RAIRO Operations Research, Vol. 42, 2008, pp. 87-103.

6.A Aboussoror, S Adly, and V Jalby, Weak nonlinear bilevel problems: existence of solutions via reverse convex and convex maximization problems, Journal of Industrial and Management Optimization, Vol. 7, 2011, pp. 559-571.

7.A Aboussoror, S Adly, and FE Saissi, Strong-weak nonlinear bilevel problems: existence of solutions in a sequential setting, Set-Valued and Variational Analysis, 2016, pp. 1-20.

8.MJ Alves and CH Antunes, An illustration of different concepts of solutions in semivectorial bilevel programming, Computational Intelligence, in 2016 IEEE Symposium Series on. IEEE, 2016, pp. 1-7. (SSCI)

9.XJ Ban, S Lu, M Ferris, and HX Liu, Risk averse second best toll pricing, Transportation and Traffic Theory 2009: Golden Jubilee, Springer, US, 2009, pp. 197-218.

10.JF Bard, Practical bilevel optimization: algorithms and applications, Kluwer Academic, Dordrecht, 1998.

11.O Ben-Ayed, Bilevel linear programming, Computers Operations Research, Vol. 20, 1993, pp. 485-501.

12.G Brown, M Carlyle, J Salmeron, and K Wood, Defending critical infrastructure, Interfaces, Vol. 36, No. 6, 2006, pp. 530-544.

13.A Caprara, M Carvalho, A Lodi, and GJ Woeginger, Bilevel knapsack with interdiction constraints, INFORMS Journal on Computing, Vol. 28, No. 2, 2016, pp. 319-333.

14.M C̆ervinka, C Matonoha, and JV Outrata, On the computation of relaxed pessimistic solutions to MPECs, Optimization Methods and Software, Vol. 28, 2013, pp. 186-206.

15.B Colson, P Marcotte, and G Savard, Bilevel programming: a survey, 4OR: A Quarterly Journal of Operations Research, Vol. 3, No. 2, 2005, pp. 87-107.

16.B Colson, P Marcotte, and G Savard, An overview of bilevel optimization, Annals of Operations Research, Vol. 153, 2007, pp. 235-256.

17.S Dassanayaka, Methods of variational analysis in pessimistic bilevel programming, Wayne State University, 2010. PhD Thesis,

18.S Dempe, Foundations of bilevel programming, Non-convex Optimization and its Applications Series, Kluwer Academic, Dordrecht, 2002.

19.S Dempe, Annottated bibliography on bilevel programming and mathematical problems with equilibrium constraints, Optimization, Vol. 52, 2003, pp. 333-359.

20.S Dempe, BS Mordukhovich, and AB Zemkoho, Necessary optimality conditions in pessimistic bilevel programming, Optimization, Vol. 63, 2014, pp. 505-533.

21.S Dempe, G Luo, and S Franke, Pessimistic bilevel linear optimization, Journal of Nepal Mathematical Society, Vol. 1, 2018, pp. 1-10.

22.P Hansen, B Jaumard, and G Savard, New branch-and-bound rules for linear bilevel programming, SIAM Journal on Scientific and Statistical Computing, Vol. 13, 1992, pp. 1194-1217.

23.VV Kalashnikov, S Dempe, GA Pérez-Valdés, NI Kalashnykova, and JF Camacho-Vallejo, Bilevel programming and applications, Mathematical Problems in Engineering, 2015, pp. 1-16.

24.MB Lignola and J Morgan, Topological existence and stability for Stackelberg problems, Journal of Optimization Theory and Applications, Vol. 84, No. 1, 1995, pp. 145-169.

25.MB Lignola and J Morgan, Inner regularizations and viscosity solutions for pessimistic bilevel optimization problems, Journal of Optimization Theory and Applications, Vol. 173, No. 1, 2017, pp. 183-202.

26.B Liu, Z Wan, J Chen, and G Wang, Optimality conditions for pessimistic semivectorial bilevel programming problems, Journal of Inequalities and Applications, Vol. 41, 2014, pp. 1-26.

27.P Loridan and J Morgan, Approximate solutions for two-level optimization problems, in Trends, K Hoffman, J-B Hiriart-Urruty, C Lemarechal, and J Zowe (editors), Mathematical Optimization, International Series of Numerical Mathematics, Birkhauser Verlag, Basel, Vol. 84, 1988, pp. 181-196.

28.P Loridan and J Morgan, ε-regularized two-level optimization problems: approximation and existence results, Springer Verlag, in Optimization-Fifth French-German Conference Castel Novel 1988, 1989, pp. 99-113. Lecture Notes in Mathematics 1405,

29.P Loridan and J Morgan, New results on approximate solution in two-level optimization, Optimization, Vol. 20, No. 6, 1989, pp. 819-836.

30.P Loridan and J Morgan, Weak via strong Stackelberg problem: New results, Journal of Global Optimization, Vol. 8, 1996, pp. 263-287.

31.L Lozano and JC Smith, A value-function-based exact approach for the bilevel mixed-integer programming problem, Operations Research, Vol. 65, No. 3, 2017, pp. 768-786.

32.J Lu, C Shi, and G Zhang, On bilevel multi-follower decision making: general framework and solutions, Information Sciences, Vol. 176, No. 11, 2006, pp. 1607-1627.

33.J Lu, G Zhang, J Montero, and L Garmendia, Multifollower trilevel decision making models and system, IEEE Transactions on Industrial Informatics, Vol. 8, No. 4, 2012, pp. 974-985.

34.J Lu, J Han, Y Hu, and G Zhang, Multilevel decision-making: a survey, Information Sciences, Vol. 346–347, 2016, pp. 463-487.

35.R Lucchetti, F Mignanego, and G Pieri, Existence theorems of equilibrium points in Stackelberg games with constraints, Optimization, Vol. 18, 1987, pp. 857-866.

36.AV Malyshev and AS Strekalovskii, Global search for pessimistic solution in bilevel problems, S Cafieri, BG Toth, EMT Hendrix, L Liberti, and F Messine (editors), in Proceedings of the Toulouse Global Optimization Workshop, 2010, pp. 77-80.

37.A Marhfour, Mixed solutions for weak Stackelberg problems: existence and stability results, Journal of Optimization Theory and Applications, Vol. 105, 2000, pp. 417-440.

38.M Sakawa and I Nishizaki, Cooperative and noncooperative multi-level programming, Springer Science and Business Media, 2009.

39.M Sakawa and I Nishizaki, Interactive fuzzy programming for multi-level programming problems: a review, Int. J. Multicrit. Decis. Making, Vol. 2, 2012, pp. 241-266.

40.A Sinha, P Malo, and K Deb, Evolutionary bilevel optimization: an introduction and recent advances, Recent Advances in Evolutionary Multi-objective Optimization, Springer International Publishing, 2017, pp. 71-103.

41.A Sinha, P Malo, and K Deb, A review on bilevel optimization: from classical to evolutionary approaches and applications, IEEE Transactions on Evolutionary Computation.

42.HV Stackelberg, The theory of market economy, Oxford University Press, Oxford, 1952.

43.A Tsoukalas, W Wiesemann, and B Rustem, Global optimisation of pessimistic bi-level problems, PM Pardalos and TF Coleman (editors), Lectures on Global Optimization, Americal Mathematical Society, Providence, RI, 2009, pp. 215-243. Fields Inst. Commun. 55,

44.L Vicente and P Calamai, Bilevel and multilevel programming: a bibliography review, Journal of Global Optimization, Vol. 5, 1994, pp. 291-306.

45.UP Wen and ST Hsu, Linear bi-level programming problems-a review, Journal of the Operational Research Society, Vol. 42, No. 2, 1991, pp. 125-133.

46.W Wiesemann, A Tsoukalas, P Kleniati, and B Rustem, Pessimistic bi-level optimisation, SIAM Journal on Optimization, Vol. 23, 2013, pp. 353-380.

47.RK Wood, Bilevel network interdiction models: Formulations and solutions, Wiley Encyclopedia of Operations Research and Management Science, 2011.

48.B Zeng, Easier than we thought-a practical scheme to compute pessimistic bilevel optimization problem, University of Pittsburgh, 2015. Technical report, available in optimization-online.org,

49.G Zhang, J Lu, and Y Gao, Multi-level decision making: models, methods and applications, Springer, Berlin, 2015.

50.G Zhang, J Han, and J Lu, Fuzzy bi-level decision-making techniques: a survey, International Journal of Computational Intelligence Systems, Vol. 9, 2016, pp. 25-34.

51.Y Zheng, Z Wan, K Sun, and T Zhang, An exact penalty method for weak linear bilevel programming problem, Journal of Applied Mathematics and Computing, Vol. 42, 2013, pp. 41-49.

52.Y Zheng, D Fang, and Z Wan, A solution approach to the weak linear bilevel programming problems, Optimization, Vol. 7, 2016, pp. 1437-1449.

53.Y Zheng, G Zhang, J Han, and J Lu, Pessimistic bilevel optimization model for risk-averse production-distribution planning, Information Sciences, Vol. 372, 2016, pp. 677-689.

54.Y Zheng, Z Zhu, and L Yuan, Partially-shared pessimistic bilevel multi-follower programming: concept, algorithm, and application, Journal of Inequalities and Applications, 2016, pp. 1-13.

55.Y Zheng, X Zhuo, and J Chen, Maximum entropy approach for sloving pessimistic bilevel programming problems, Wuhan University Journal of Natural Sciences, Vol. 1, 2017, pp. 63-67.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 11 - 1
Pages: 725 - 736
Publication Date: 2018/03/09
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.11.1.56 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - June Liu
AU  - Yuxin Fan
AU  - Zhong Chen
AU  - Yue Zheng
PY  - 2018
DA  - 2018/03/09
TI  - Pessimistic Bilevel Optimization: A Survey
JO  - International Journal of Computational Intelligence Systems
SP  - 725
EP  - 736
VL  - 11
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.11.1.56
DO  - 10.2991/ijcis.11.1.56
ID  - Liu2018
ER  -

download .riscopy to clipboard