S. Dempe, A. Zemkoho (eds.)Bilevel OptimizationSpringer Optimization and Its Applications161https://doi.org/10.1007/978-3-030-52119-6_14

14. Methods for Pessimistic Bilevel Optimization

June Liu¹, Yuxin Fan², Zhong Chen³ and Yue Zheng¹

(1)

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

(2)

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

(3)

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

Zhong Chen

Email: chenzhong@yangtzeu.edu.cn

Abstract

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. The goal of this chapter is to provide a extensive review on pessimistic bilevel optimization from basic models, definitions and properties to solution approaches. It will directly support researchers in understanding theoretical research results, designing solution algorithms in relation to pessimistic bilevel optimization.

Keywords

Pessimistic bilevel optimizationStackelberg gameRisk-averse

14.1 Introduction

Bilevel decision-making problems [11, 20, 46, 57], motivated by Stackelberg game theory [50], 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 [21]. Note that a linear bilevel programming problem was proved to be strongly NP-hard [25]. Therefore, solving such a problem is not an easy task.

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle ``\min \limits_{\boldsymbol{x}}"&\displaystyle F(\boldsymbol{x},\boldsymbol{y}){}\\ &\displaystyle \mbox{s.t.}&\displaystyle G(\boldsymbol{x})\le 0, \boldsymbol{y}\in \Psi(\boldsymbol{x}), \end{array} \end{aligned}$

(14.1.1)

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}}&\displaystyle f(\boldsymbol{x},\boldsymbol{y}) \\ &\displaystyle \mbox{s.t.}&\displaystyle g(\boldsymbol{x},\boldsymbol{y})\le 0, \end{array} \end{aligned}$

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 problem (14.1.1).

To overcome this situation, the majority of authors used optimistic formulation and pessimistic formulation, which represent the two different situations between the leader and the follower. In the optimistic formulation (e.g., see Ref. [20] and the references therein), the follower always selects a strategy in Ψ(x) that suits the leader best. Alternatively, pessimistic formulation (e.g., see Ref. [20] and the references therein) refers to the case where the leader protects himself against the worst possible situation.

There are several survey papers on bilevel/multilevel programming/decision-making in the past 20 years. However, these surveys focus on an optimistic bilevel optimization. For example, Ben-Ayed [12], Wen and Hsu [53] presented the basic models, solution definitions, solution approaches and applications of the optimistic linear bilevel optimization. Colson et al. [17, 18], Vicente and Calamai [52] focused on traditional solution concepts and solution approaches for the optimistic bilevel programming problems. Dempe [21] summarized the main research directions and the main fields of applications of bilevel programming, but mainly fixed attention on the optimistic formulation. Kalashnikov et al. [26] presented a survey of bilevel programming and application area.

Sakawa and Nishizaki [47] reviewed interactive fuzzy programming approaches for the optimistic bilevel/multilevel programming problems which focus on cooperative decision-making in decentralised organizations. Zhang et al. [58] reviewed the fuzzy bilevel decision-making techniques which include models, approaches and systems.

Lu et al. [40] identified nine different kinds of relationships amongst followers by establishing a general framework for bilevel multi-follower decision problems in which the lower level problem has multiple followers. Furthermore, Lu et al. [41] analyzed various kinds of relationships between decision entities in a multi-follower 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. [42] developed the latest research on multilevel decision-making involving theoretical research results and applications.

Sinha et al. [48] presented an introduction to progress made by evolutionary computation towards handing bilevel optimization. Sinha et al. [49] developed a comprehensive review on bilevel optimization from classical to evolutionary approaches, and then discussed a number of potential application problems.

The above surveys papers have provided good references on optimistic bilevel optimization for researchers. Recently, Liu et al. [32] proposed an extensive review on pessimistic bilevel optimization from basic definitions and properties to solution approaches. This chapter will add some models and the latest newly published articles of pessimistic bilevel optimization on the basis of [32].

The remainder of the chapter is organized as follows. In Sect. 14.2, we describe the classification of pessimistic bilevel optimization. In Sects. 14.3 and 14.4, we review definitions and properties of pessimistic bilevel optimization. In Sect. 14.5, some solution approaches are proposed for pessimistic bilevel optimization. Finally, we conclude this chapter and provide some future directions in Sect. 14.6.

14.2 Classification of Pessimistic Bilevel Optimization

In this section, we describe the classification of pessimistic bilevel optimization into two main categories: pessimistic bilevel programming problems (in their general and linear versions) and further generalizations (semivectorial and multi-follower problems) of pessimistic bilevel optimization.

14.2.1 Pessimistic Bilevel Programming Problems

14.2.1.1 Pessimistic Linear Bilevel Programming Problems

Pessimistic linear bilevel programming problems are pessimistic bilevel optimization problems in which the objective functions of the leader and the follower and their constraint regions are restricted to be affine. Mathematically, pessimistic linear bilevel programming problems are stated as follows:

$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X} \max \limits_{\boldsymbol{y}\in \Psi(\boldsymbol{x})}\ \boldsymbol{c}^{\top}\boldsymbol{x}+\boldsymbol{d}^{\top}\boldsymbol{y}{} \end{array} \end{aligned}$

(14.2.1)

where X is a closed subset of R ⁿ, and Ψ(x) is the set of solutions to the lower level problem

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}\ge 0}&\displaystyle \boldsymbol{w}^{\top}\boldsymbol{y}\\ &\displaystyle \mbox{s.t.} &\displaystyle B\boldsymbol{y} \le \boldsymbol{b} - A\boldsymbol{x} \end{array} \end{aligned}$

where c, x ∈ R ⁿ, d, w, y ∈ R ^m, A ∈ R ^p×n, B ∈ R ^p×m, and b ∈ R ^p.

Problem (14.2.1) is often called weak linear bilevel programming problem [4]. Note that, when the lower level problem satisfies A = 0, i.e. the follower’s feasible region does not depend on the upper level decision variables, problem (14.2.1) can be called a independent pessimistic linear bilevel programming problem.

14.2.1.2 General Pessimistic Bilevel Programming Problems

General pessimistic bilevel programming problems can be formulated as follows:

$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X^{\prime}} \max \limits_{\boldsymbol{y}\in \Psi(\boldsymbol{x})}\ F(\boldsymbol{x},\boldsymbol{y}).{} \end{array} \end{aligned}$

(14.2.2)

where X ^′ := {x : G(x) ≤ 0}, and Ψ(x) is the set of solutions to the lower level problem

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

When the feasible set of the follower does not depend on the upper level decision variables, i.e., g(x, y) in problem (14.2.2) is reduced to g(y), problem (14.2.2) is referred as an independent pessimistic bilevel problem [54]. Note that it is also called weak Stackelberg problem in Ref. [38].

14.2.2 Further Generalizations of Pessimistic Bilevel

14.2.2.1 Pessimistic Semivectorial Bilevel Programming Problems

Pessimistic semivectorial bilevel programming problems [8] are pessimistic bilevel optimization problems in which the lower level problem is a multiobjective optimization problem. Mathematically, pessimistic semivectorial bilevel programming problems can be formulated as follows:

$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X^{\prime}} \max \limits_{\boldsymbol{y}\in \Psi_{Ef}(\boldsymbol{x})}\ F(\boldsymbol{x},\boldsymbol{y}).{} \end{array} \end{aligned}$

(14.2.3)

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}}&\displaystyle (f_1(\boldsymbol{x},\boldsymbol{y}),f_2(\boldsymbol{x},\boldsymbol{y}),\cdots,f_q(\boldsymbol{x},\boldsymbol{y})) \\ &\displaystyle \mbox{s.t.}&\displaystyle g(\boldsymbol{x},\boldsymbol{y})\le 0. \end{array} \end{aligned}$

14.2.2.2 Pessimistic Bilevel Multi-Follower Programming Problems

Pessimistic bilevel multi-follower programming problems are pessimistic bilevel optimization problems in which the lower level problem has multiple followers. When multiple followers are involved in a pessimistic bilevel optimization, different relationships among these followers could cause multiple different processes for deriving a solution for the leader. Here three decision models are established and described respectively as follows.

(I)
Uncooperative pessimistic linear bilevel multi-follower programming problem [61]. For such a problem, M followers are involved and there is no shared decision variable, objective function or constrain function among them.
$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X}\ [\boldsymbol{c}^\top \boldsymbol{x}+\sum_{i=1}^M\max \limits_{\boldsymbol{y}_i\in \Psi_i(\boldsymbol{x})}\ \boldsymbol{d}_i^\top \boldsymbol{y}_i]{} \end{array} \end{aligned}$

(14.2.4)

where Ψ_i(x) is the set of solutions to the ith follower’s problem
$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}_i\ge 0}&\displaystyle \boldsymbol{w}_i^\top \boldsymbol{y}_i \\ &\displaystyle \mbox{s.t.} &\displaystyle A_i\boldsymbol{x}+B_i\boldsymbol{y}_i\le \boldsymbol{b}_i. \end{array} \end{aligned}$

Here x, c ∈ R ⁿ, $\boldsymbol {y}_i,\boldsymbol {d}_i,\boldsymbol {w}_i\in R^{m_i}$ , $A_i\in R^{q_i\times n}$ , $B_i\in R^{q_i\times {m_i}}$ , $\boldsymbol {b}_i\in R^{q_i}$ , and i = 1, 2, …, M.
(II)
Pessimistic linear bilevel multi-follower programming problem with partially shared variables among followers [62]. For such a problem, M followers are involved and there is a partially shared decision variable v.
$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X}\ \max \limits_{{(\boldsymbol{y}_i,\boldsymbol{v})\in \Psi_i(\boldsymbol{x})}}\ [\boldsymbol{c}^\top \boldsymbol{x}+\sum_{i=1}^M\boldsymbol{d}_i^\top \boldsymbol{y}_i+\boldsymbol{s}^\top \boldsymbol{v}]{} \end{array} \end{aligned}$

(14.2.5)

where Ψ_i(x) is the set of solutions of the ith follower’s problem
$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}_i,\boldsymbol{v}}\ &\displaystyle \boldsymbol{w}_i^\top \boldsymbol{y}_i+\boldsymbol{z}_i^\top \boldsymbol{v} \\ &\displaystyle \mbox{s.t.} &\displaystyle A_i\boldsymbol{x}+B_i\boldsymbol{y}_i+C_i\boldsymbol{v}\leq \boldsymbol{b}_i,\\ &\displaystyle &\displaystyle \boldsymbol{y}_i,\boldsymbol{z}\geq 0. \end{array} \end{aligned}$

Here s, v, z _i ∈ R ^l, $C_i\in R^{q_i\times l}$ and i = 1, 2, …, M.
(III)
Pessimistic referential-uncooperative linear bilevel multi-follower programming problem. For such a problem, M followers are involved in a referential-uncooperative situation, i.e. these followers are uncooperative and they do cross reference information by considering other followers’ decision results in each of their own decision objectives and constraints.
$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}} &\displaystyle [ \boldsymbol{c}^\top \boldsymbol{x}+\sum_{i=1}^{M}\max_{\boldsymbol{y}_i\in \Psi_i(\boldsymbol{x},\boldsymbol{y}_{-i})}\ \boldsymbol{d}_i^\top \boldsymbol{y}_i]{} \end{array} \end{aligned}$

(14.2.6)

where y _−i = (y ₁, ⋯ , y _i−1, y _i+1, ⋯ , y _M) and Ψ_i(x, y _−i) is the set of solutions of the ith follower’s problem
$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}_i\geq 0} &\displaystyle \boldsymbol{w}_i^\top \boldsymbol{y}_i \\ &\displaystyle \mbox{s.t.} &\displaystyle A_i\boldsymbol{x}+\sum_{j=1}^{M}B_{ij}\boldsymbol{y}_j\leq \boldsymbol{b}_i. \end{array} \end{aligned}$

Here $B_{ij}\in R^{q_i\times m_j}$ and i = 1, 2, ⋯ , M.

14.3 Definitions of Pessimistic Bilevel Optimization

To understand and analyze solution approaches of pessimistic bilevel optimization, this section reviews the notations and definitions of problem (14.2.2).

14.3.1 Definitions

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

Definition 14.3.1

1.
Constraint region of problem (14.2.2):
$\displaystyle \begin{aligned} \begin{array}{rcl} S:=\{(\boldsymbol{x},\boldsymbol{y}):G(\boldsymbol{x})\le 0, g(\boldsymbol{x},\boldsymbol{y})\le 0\}. \end{array} \end{aligned}$
2.
Projection of S onto the leader’s decision space:
$\displaystyle \begin{aligned} \begin{array}{rcl} S(X):=\{\boldsymbol{x}\in X: \exists \boldsymbol{y}, \mbox{such that}\ (\boldsymbol{x},\boldsymbol{y})\in S\}. \end{array} \end{aligned}$
3.
Feasible set for the follower ∀x ∈ S(X):
$\displaystyle \begin{aligned} \begin{array}{rcl} Y(\boldsymbol{x}):=\{\boldsymbol{y}: g(\boldsymbol{x},\boldsymbol{y})\le 0\}. \end{array} \end{aligned}$
4.
The follower’s rational reaction set for x ∈ S(X):
$\displaystyle \begin{aligned} \begin{array}{rcl} \Psi(\boldsymbol{x}):=\{\boldsymbol{y}: \boldsymbol{y}\in \mbox{arg}\min [f(\boldsymbol{x},\boldsymbol{y}): \boldsymbol{y}\in Y(\boldsymbol{x})] \}. \end{array} \end{aligned}$
5.
Inducible region or feasible region of the leader:
$\displaystyle \begin{aligned} \begin{array}{rcl} \mbox{IR}:=\{(\boldsymbol{x},\boldsymbol{y}): (\boldsymbol{x},\boldsymbol{y})\in S, \boldsymbol{y}\in \Psi(\boldsymbol{x})\}. \end{array} \end{aligned}$

△

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

$\displaystyle \begin{aligned}\varphi(\boldsymbol{x}):=\sup \limits_{\boldsymbol{y}\in \Psi(\boldsymbol{x})}\ F(\boldsymbol{x},\boldsymbol{y}).\end{aligned}$

Definition 14.3.2

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

$\displaystyle \begin{aligned} \begin{array}{rcl} \varphi(\boldsymbol{x}^*)&\displaystyle =&\displaystyle F(\boldsymbol{x}^*,\boldsymbol{y}^*),\\ \varphi(\boldsymbol{x}^*)&\displaystyle \le&\displaystyle \varphi(\boldsymbol{x}), \ \forall\ \boldsymbol{x} \in X. \end{array} \end{aligned}$

△

In the following, some definitions concerning, in particular, approximate solutions (𝜖-Stackelberg solution, 𝜖-Stackelberg equilibrium pair) to the weak Stackelberg problem will be described.

Definition 14.3.3 (Loridan and Morgan [35])

Any point x ^∗ verifying v ₁ = φ(x ^∗) is called a Stackelberg solution to the weak Stackelberg problem. Here, $v_1:=\inf \limits _{\boldsymbol {x}\in X}\ \varphi (\boldsymbol {x}).$ △

Definition 14.3.4 (Loridan and Morgan [35])

A pair (x ^∗, y ^∗) verifying v ₁ = φ(x ^∗) and y ^∗∈ Ψ(x ^∗) is called a Stackelberg equilibrium pair.△

Definition 14.3.5 (Loridan and Morgan [35])

Let 𝜖 > 0 be a given number. A point x ^∗ is an 𝜖-Stackelberg solution if and only if x ^∗∈ X and φ(x ^∗) ≤ v ₁ + 𝜖.△

Definition 14.3.6 (Loridan and Morgan [35])

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[8] presented and illustrated a definition of the solution of pessimistic semivectorial bilevel problem (14.2.3), and made comparison of optimistic solution, pessimistic solution, deceiving solution and rewarding solution.

14.4 Properties of Pessimistic Bilevel Optimization

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

14.4.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 et al. [43] who proposed some examples that fail to have a solution. Moreover, the most studies have been devoted to the weak Stackelberg problem. Aboussoror and Loridan [3], Aboussoror [1] have given sufficient conditions to obtain the existence of solutions to the weak Stackelberg problem via a regularized scheme. Any accumulation point of a sequence of regularized solutions is a solution to the weak Stackelberg problem. Aboussoror and Mansouri [5] have deduced the existence of solutions to the weak Stackelberg problem via d.c. problems. Similar results using reverse convex and convex maximization problems are given in Aboussoror et al. [6].

Loridan and Morgan [35] have obtained some results for approximate solutions of the weak Stackelberg 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 Stackelberg problem. The interested reader can refer to the references about the approximate solutions of the weak Stackelberg problem. Furthermore, Loridan and Morgan [36] improved and extended some properties proposed in Ref. [35]. Similar results using approximation scheme were given in Ref. [37].

Lignola and Morgan [28] 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 [45] 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 pessimistic linear bilevel programming problems, using the strong dual theorem of linear programming and penalty method, Aboussoror and Mansouri [4] have established the existence results of solutions. Note that, the strong-weak Stackelberg problems have been reduced the weak Stackelberg problem under some conditions. Aboussoror and Loridan [2] have studied the existence of solutions of strong-weak Stackelberg problems. In particular, using the regularization and the notion of variational convergence, Aboussoror [7] have given sufficient conditions to ensure the existence of solutions to such problems. The obtained results in Refs. [2] and [7] can be applied to the weak Stackelberg problem by deleting some variables.

When the pessimistic bilevel optimization problem (14.2.2) 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 [29] 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. More recently, Lignola and Morgan [30] continue this research by considering a new inner regularizations of the lower level problem which not necessarily satisfy the constraints, and by deriving an existence result of related viscosity solutions to pessimistic bilevel optimization.

14.4.2 Optimality Conditions and Complexity

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 [19] using implicit programming approach, minmax programming approach and duality programming approach respectively. Using the advanced tools of variational analysis and generalized differentiation, Dempe [22] 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. Using the two-level value function approach, Dempe et al. [24] derived the results on sensitivity analysis and necessary optimality conditions of pessimistic bilevel optimization with nonsmooth data.

In addition, Liu et al. [31] presented the first order necessary optimality conditions of a class of pessimistic semivectorial bilevel optimization. Recently, Lampariello et al. [27] discussed the relations among the perturbed pessimistic bilevel problem, pessimistic bilevel optimization and the two follower game as well as the mathematical program with complementarity constraints with respect to their global minimal points. They also presented the connections between their local minimal points in detail. Aussel and Svensson [9] discussed the relations of global and local solutions of both pessimistic bilevel optimization problem and the associated pessimistic mathematical program with complementarity constraints problem. These various necessary optimality conditions and connections to other optimization problems could be helpful to develop fast algorithms to obtain solutions of pessimistic bilevel optimization.

The computational complexity of pessimistic bilevel optimization is easily confirmed at its simplest version, i.e. pessimistic linear bilevel problem. Under the certain assumptions, Wiesemann et al.[54] obtained that: (a) the independent pessimistic linear bilevel programming problem (14.2.1) can be solved in polynomial time; (b) if m, the number of the lower level decision variables, is constant, the pessimistic linear bilevel programming problem (14.2.1) can be solved in polynomial time. If m is nonconstant, it is strongly NP-hard. These results also imply that a general pessimistic bilevel programming problem is strongly NP-hard if the the number of the lower level decision variables is nonconstant.

14.5 Solution Approaches of Pessimistic Bilevel Optimization

14.5.1 Penalty Method

At present, penalty methods [4, 59] were used to solve the pessimistic linear bilevel programming problems. An initial step in this direction was developed by Aboussoror and Mansouri [4]. Using the strong dual theory of linear programming and penalty methods, they transformed problem (14.2.1) into a single-level optimization problem:

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}, \boldsymbol{t}, \boldsymbol{u}}&\displaystyle \boldsymbol{c}^{\top}\boldsymbol{x} + \boldsymbol{w}^{\top}\boldsymbol{t} + (\boldsymbol{b}-A\boldsymbol{x})^{\top}\boldsymbol{u}{}\\ &\displaystyle \mbox{s.t.}&\displaystyle -B^{\top}\boldsymbol{u} \le k\boldsymbol{w}-\boldsymbol{d}, \\ &\displaystyle &\displaystyle B\boldsymbol{t}\le k(\boldsymbol{b}-A\boldsymbol{x}),\\ &\displaystyle &\displaystyle \boldsymbol{x}\in X, \boldsymbol{t}, \boldsymbol{u}\ge 0, \end{array} \end{aligned}$

(14.5.1)

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

Under some assumptions, Aboussoror and Mansouri [4] 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 problem (14.5.1), x _k solves problem (14.2.1). Unfortunately, no numerical results were reported.

A more recent contribution by Zheng et al. [59], follows the ideas of Aboussoror and Mansouri [4], who presented a new variant of the penalty method to solve problem (14.2.1). Their method transformed it into the following penalty problem:

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}, \boldsymbol{t}, \boldsymbol{u}}&\displaystyle \boldsymbol{c}^{\top}\boldsymbol{x} + k\boldsymbol{w}^{\top}\boldsymbol{y} + (\boldsymbol{b}-A\boldsymbol{x})^{\top}\boldsymbol{u}{}\\ &\displaystyle \mbox{s.t.}&\displaystyle -B^{\top}\boldsymbol{u} \le k\boldsymbol{w}-\boldsymbol{d}, \\ &\displaystyle &\displaystyle B\boldsymbol{y}\le \boldsymbol{b}-A\boldsymbol{x},\\ &\displaystyle &\displaystyle \boldsymbol{x}\in X, \boldsymbol{y}, \boldsymbol{u}\ge 0, \end{array} \end{aligned}$

(14.5.2)

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

Replacing the lower level problem with its Kuhn-Tucker optimality condition, Liu et al. [33] transformed problem (14.2.1) into another single-level optimization problem, and investigated the relation of the solution of those problems. In addition, Zheng et al. proposed penalty methods to solve uncooperative pessimistic linear bilevel multi-follower programming problem [61] and pessimistic linear bilevel multi-follower programming problem with partially shared variables among followers [62] respectively.

14.5.2 Kth-Best Algorithm

An important property of the solution to the pessimistic linear bilevel programming problem (14.2.1) is that there exists a solution which occurs at a vertex of the polyhedron W. Here W is the constraint region of problem (14.2.1), i.e.

$\displaystyle \begin{aligned}W:=\{(\boldsymbol{x},\boldsymbol{y}): \boldsymbol{x}\in X, B\boldsymbol{y}\le \boldsymbol{b}-A\boldsymbol{x}, \boldsymbol{y}\ge 0\}.\end{aligned}$

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

Zheng et al. [60] first proposed a modified version of Kth-Best algorithm to the pessimistic linear bilevel optimization problems. 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 problem (14.2.1) if it is yes. Otherwise, the next one will be selected and checked.

14.5.3 Approximation Approach

As is well-known, approximation solution of the independent pessimistic bilevel problems have in fact a long history that dates back at least to papers [28, 37]. For recent surveys and improvements about this topic, see also [15, 29, 30]. These results may provide the reader with an idea to design new algorithms for the pessimistic bilevel programming problems, although the authors in [15, 28–30, 37] did not present the direct algorithms.

In the following, we will consider the perturbed pessimistic bilevel programming problems (PBP_𝜖) [27] which can be formulated as follows:

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}\in X^{\prime}} \max \limits_{\boldsymbol{y}\in \Psi_{\epsilon}(\boldsymbol{x})}&\displaystyle F(\boldsymbol{x},\boldsymbol{y}).{} \end{array} \end{aligned}$

(14.5.3)

where 𝜖 > 0, Ψ_𝜖(x) := {y : f(x, y) ≤ ϕ(x) + 𝜖}. Note that ϕ(x) is the optimal value function of the lower level problem

To solve the above perturbed pessimistic bilevel programming problem, Lampariello et al. [27] first presented the perturbed standard pessimistic bilevel problem (SPBP_𝜖):

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}, \boldsymbol{y}} &\displaystyle F(\boldsymbol{x},\boldsymbol{y})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{x}\in X^{\prime}, \boldsymbol{y}\in R_{\epsilon}(\boldsymbol{x}), \end{array} \end{aligned}$

where R _𝜖(x) is the set of 𝜖-solutions of the following optimization problem

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \max \limits_{\boldsymbol{w}} &\displaystyle F(\boldsymbol{x},\boldsymbol{w})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{w}\in \Psi_{\epsilon}(\boldsymbol{x}), \end{array} \end{aligned}$

and then by using Multi Follower Game with two followers, proposed an optimistic bilevel problem in which the lower level is a parametric GNEP with two players (MFG_𝜖):

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}} &\displaystyle F(\boldsymbol{x},\boldsymbol{y})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{x}\in X^{\prime}, (\boldsymbol{y},\boldsymbol{z})\in E_{\epsilon}(\boldsymbol{x}), \end{array} \end{aligned}$

where E _𝜖(x) is the equilibrium set of the following GNEP:

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}} &\displaystyle -F(\boldsymbol{x},\boldsymbol{y})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{y}\in Y(\boldsymbol{x}), \\ &\displaystyle &\displaystyle f(\boldsymbol{x},\boldsymbol{y})\le f(\boldsymbol{x},\boldsymbol{z})+ \epsilon, \end{array} \end{aligned}$

and

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{z}} &\displaystyle f(\boldsymbol{x},\boldsymbol{z})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{z}\in Y(\boldsymbol{x}). \end{array} \end{aligned}$

Using the KKT conditions, (MFG_𝜖) can be transformed into a single-level Mathematical Program with Complementarity Constraints (MPCC_𝜖) problem. Under some assumptions, Lampariello et al. [27] concluded the relations among (PBP_𝜖), (SPBP_𝜖), (MFG_𝜖) and (MPCC_𝜖). This would provide the readers with a new way to discuss the perturbed pessimistic bilevel programming problems.

When the follower’s feasible region does not depend on the upper level decision variables, the above perturbed pessimistic bilevel programming problem also can be called independent perturbed pessimistic bilevel programming problem. It is formulated as follows:

$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X^{\prime}} \sup \limits_{\boldsymbol{y}\in \Psi_{\epsilon}(\boldsymbol{x})}\ F(\boldsymbol{x},\boldsymbol{y}){} \end{array} \end{aligned}$

(14.5.4)

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}}&\displaystyle f(\boldsymbol{x},\boldsymbol{y})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{y}\in Y, \end{array} \end{aligned}$

Several authors presented some approximation approaches. For example, Loridan and Morgan [38] first presented the following strong Stackelberg problem:

$\displaystyle \begin{aligned} \begin{array}{rcl} \min \limits_{\boldsymbol{x}\in X^{\prime}} \inf \limits_{y\in \Psi(\boldsymbol{x},\beta,\gamma)}\ F(\boldsymbol{x},\boldsymbol{y}){} \end{array} \end{aligned}$

(14.5.5)

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{y}}&\displaystyle l(\boldsymbol{x},\boldsymbol{y},\beta)\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{y}\in Y, \end{array} \end{aligned}$

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

Based on the Molodtsov method, they computed a sequence of solutions of strong Stackelberg problem (14.5.5) 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 perturbed pessimistic bilevel problem.

On the other hand, Tsoukalas et al. [51], Wiesemann et al. [54] considered the following independent pessimistic bilevel optimization problem:

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}\in X}&\displaystyle H(\boldsymbol{x}){}\\ &\displaystyle \mbox{s.t.}&\displaystyle g(\boldsymbol{x},\boldsymbol{y})\le 0, \forall \boldsymbol{y} \in \mbox{arg}\max \limits_{\boldsymbol{y}^{\prime} \in Y} h(\boldsymbol{x},\boldsymbol{y}^{\prime}). \end{array} \end{aligned}$

(14.5.6)

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x}\in X^{\prime}}&\displaystyle H(\boldsymbol{x})\\ &\displaystyle \mbox{s.t.}&\displaystyle g(\boldsymbol{x},\boldsymbol{y})\le 0, \forall \boldsymbol{y} \in Y_{\epsilon}(\boldsymbol{x}),\\ &\displaystyle &\displaystyle Y_{\epsilon}(\boldsymbol{x}) = \{\boldsymbol{z}\in Y: h(\boldsymbol{x},\boldsymbol{z})< h(\boldsymbol{x},\boldsymbol{z}^{\prime})+ \epsilon, \forall \boldsymbol{z}^{\prime}\in Y\}, \\ &\displaystyle &\displaystyle \boldsymbol{x}\in X. \end{array} \end{aligned}$

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

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x},\boldsymbol{z},\lambda}&\displaystyle H(\boldsymbol{x})\\ &\displaystyle \mbox{s.t.}&\displaystyle \lambda(\boldsymbol{y})[h(\boldsymbol{x},\boldsymbol{z})-h(\boldsymbol{x},\boldsymbol{y})+\epsilon] \\ &\displaystyle &\displaystyle + (1-\lambda(\boldsymbol{y}))g(\boldsymbol{x},\boldsymbol{y})\le 0, \forall \boldsymbol{y}\in Y, \\ &\displaystyle &\displaystyle \boldsymbol{x}\in X^{\prime}, \boldsymbol{z}\in Y, \lambda: Y \longrightarrow [0,1], \end{array} \end{aligned}$

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 et al. [16] 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.

14.5.4 Reduction Method

Again, to solve problem (14.2.2), Zeng [56] presented its relaxation problem as follows:

$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle \min \limits_{\boldsymbol{x},\bar{\boldsymbol{y}}}\max \limits_{\boldsymbol{y}\in \tilde{Y}(\boldsymbol{x},\bar{\boldsymbol{y}})}&\displaystyle F(\boldsymbol{x},\boldsymbol{y})\\ &\displaystyle \mbox{s.t.}&\displaystyle \boldsymbol{x}\in X,\\ &\displaystyle &\displaystyle g(\boldsymbol{x},\bar{\boldsymbol{y}})\le 0,{}\\ &\displaystyle &\displaystyle \tilde{Y}(\boldsymbol{x},\bar{\boldsymbol{y}}):=\{\boldsymbol{y}: g(\boldsymbol{x},\boldsymbol{y})\le 0, f(\boldsymbol{x},\boldsymbol{y})\le f(\boldsymbol{x},\bar{\boldsymbol{y}})\}. \end{array} \end{aligned}$

(14.5.7)

Proposition 3 in Ref. [56] means that if $(\boldsymbol {x}^*,\bar {\boldsymbol {y}}^{\prime },\boldsymbol {y}^{\prime })$ is a solution to problem (14.5.7), then there exists a point y ^∗ ∈ Ψ(x ^∗) such that (x ^∗, y ^∗) solves problem (14.2.2). 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.

Moreover, Zheng et al. [64] proposed a reducibility method for a pessimistic linear bilevel programming problem which is reduced to disjoint bilinear programming problems. For a pessimistic quadratic-linear bilevel optimization problem, Malyshev and Strekalovsky [44] reduced it to a series of optimistic bilevel optimization problems and then developed the global and local search algorithms.

In addition to the above several methods, for the pessimistic linear bilevel programming problem, Dempe et al. [23] proposed the global and local search algorithms via the value method and the strong dual theory of linear programming; Liu et al. [34] presented a new algorithm which embeds a penalty method into a branch and bound algorithm. For the pessimistic bilevel mixed-integer programming problems, Lozano and Smith [39] developed two methods (i.e. two-phase approach and cutting-plane algorithm) based on an optimal-value-function reformulation. Zheng et al. [63] presented a maximum entropy approach to solve a class of 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.

14.6 Conclusions and Prospective Research Topics

Pessimistic bilevel optimization plays an exceedingly important role in different application fields, such as second best toll pricing [10], production-distribution planning [61], principal-agent [54] and interdiction game [13, 14, 55]. In this chapter, we have addressed pessimistic bilevel optimization. This chapter gives an overview on the state-of-the-art of pessimistic bilevel optimization. Based on the above discussion, 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 pessimistic linear 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.

Acknowledgement

This work was partially supported by the National Natural Science Foundation of China (Nos. 11871383 and 11501233).

References

1.
A. Aboussoror, Weak bilevel programming problems: existence of solutions. Adv. Math. Res. 1, 83–92 (2002)
2.
A. Aboussoror, P. Loridan, Strong-weak Stackelberg problems in finite dimensional spaces. Serdica Math. J. 21, 151–170 (1995)
3.
A. Aboussoror, P. Loridan, Existence of solutions to two-level optimization problems with nonunique lower-level solutions. J. Math. Anal. Appl. 254, 348–357 (2001)
4.
A. Aboussoror, A. Mansouri, Weak linear bilevel programming problems: existence of solutions via a penalty method. J. Math. Anal. Appl. 304, 399–408 (2005)
5.
A. Aboussoror, A. Mansouri, Existence of solutions to weak nonlinear bilevel problems via MinSup and d.c. problems. RAIRO Oper. Res. 42, 87–103 (2008)
6.
A. Aboussoror, S. Adly, V. Jalby, Weak nonlinear bilevel problems: existence of solutions via reverse convex and convex maximization problems. J. Ind. Manage. Optim. 7, 559–571 (2011)
7.
A. Aboussoror, S. Adly, F.E. Saissi, Strong-weak nonlinear bilevel problems: existence of solutions in a sequential setting. Set-Valued Var. Anal. 1, 113–132 (2017)
8.
M.J. Alves, C.H. Antunes, An illustration of different concepts of solutions in semivectorial bilevel programming, in IEEE Symposium Series on Computational Intelligence ( IEEE, New York, 2016), pp. 1–7
9.
D. Aussel, A. Svensson, Is pessimistic bilevel programming a special case of a mathematical program with complementarity constraints? J. Optim. Theory Appl. 181(2), 504–520 (2019)
10.
X.J. Ban, S. Lu, M. Ferris, H.X. Liu, Risk averse second best toll pricing, in Transportation and Traffic Theory 2009: Golden Jubilee (Springer, New York, 2009), pp. 197–218
11.
J.F. Bard, Practical Bilevel Optimization: Algorithms and Applications (Kluwer Academic, Dordrecht, 1998)
12.
O. Ben-Ayed, Bilevel linear programming. Comput. Oper. Res. 20, 485–501 (1993)
13.
G. Brown, M. Carlyle, J. Salmeron, K. Wood, Defending critical infrastructure. Interfaces 36(6), 530–544 (2006)
14.
A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger, Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2), 319–333 (2016)
15.
F. Caruso, M.B. Lignola, J. Morgan, Regularization and approximation methods in Stackelberg Games and bilevel optimization. No. 541. Centre for Studies in Economics and Finance (CSEF), University of Naples, Naples (2019)
16.
M. C̆ervinka, C. Matonoha, J.V. Outrata, On the computation of relaxed pessimistic solutions to MPECs. Optim. Methods Softw. 28, 186–206 (2013)
17.
B. Colson, P. Marcotte, G. Savard, Bilevel programming: a survey. 4OR Q. J. Oper. Res. 3(2), 87–107 (2005)
18.
B. Colson, P. Marcotte, G. Savard, An overview of bilevel optimization. Ann. Oper. Res. 153, 235–256 (2007)
19.
S. Dassanayaka, Methods of variational analysis in pessimistic bilevel programming. Wayne State University, PhD Thesis (2010)
20.
S. Dempe, Foundations of Bilevel Programming. Nonconvex Optimization and its Applications Series (Kluwer Academic, Dordrecht, 2002)
21.
S. Dempe, Annotated bibliography on bilevel programming and mathematical problems with equilibrium constraints. Optimization 52, 333–359 (2003)
22.
S. Dempe, B.S. Mordukhovich, A.B. Zemkoho, Necessary optimality conditions in pessimistic bilevel programming. Optimization 63, 505–533 (2014)
23.
S. Dempe, G. Luo, S. Franke, Pessimistic bilevel linear optimization. J. Nepal Math. Soc. 1, 1–10 (2018)
24.
S. Dempe, B.S. Mordukhovich, A.B. Zemkoho, Two-level value function approach to non-smooth optimistic and pessimistic bilevel programs. Optimization 68(2–3), 433–455 (2019)
25.
P. Hansen, B. Jaumard, G. Savard, New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13, 1194–1217 (1992)
26.
V.V. Kalashnikov, S. Dempe, G.A. Pérez-Valdés, N.I. Kalashnykova, J.F. Camacho-Vallejo, Bilevel programming and applications. Math. Probl. Eng. 2015, 1–16 (2015)
27.
L. Lampariello, S. Sagratella, O. Stein, The standard pessimistic bilevel problem. SIAM J. Optim. 29(2), 1634–1656 (2019)
28.
M.B. Lignola, J. Morgan, Topological existence and stability for Stackelberg problems. J. Optim. Theory Appl. 84(1), 145–169 (1995)
29.
M.B. Lignola, J. Morgan, Inner regularizations and viscosity solutions for pessimistic bilevel optimization problems. J. Optim. Theory Appl. 173(1), 183–202 (2017)
30.
M.B. Lignola, J. Morgan, Further on inner regularizations in bilevel optimization. J. Optim. Theory Appl. 180(3), 1087–1097 (2019)
31.
B. Liu, Z. Wan, J. Chen, G. Wang, Optimality conditions for pessimistic semivectorial bilevel programming problems. J. Inequal. Appl. 41, 1–26 (2014)
32.
J. Liu, Y. Fan, Z. Chen, Y. Zheng, Pessimistic bilevel optimization: a survey. Int. J. Comput. Intell. Syst. 11(1), 725–736 (2018)
33.
J. Liu, Y. Hong, Y. Zheng, A new variant of penalty method for weak linear bilevel programming problems. Wuhan Univ. J. Nat. Sci. 23(4), 328–332 (2018)
34.
J. Liu, Y. Hong, Y. Zheng, A branch and bound-based algorithm for the weak linear bilevel programming problems. Wuhan Univ. J. Nat. Sci. 23(6), 480–486 (2018)
35.
P. Loridan, J. Morgan, Approximate solutions for two-level optimization problems. in Trends in Mathematical Optimization, ed. by K. Hoffman, J.-B. Hiriart-Urruty, C. Lemarechal, J. Zowe. International Series of Numerical Mathematics, vol. 84 (Birkhauser Verlag, Basel, 1988), pp. 181–196
36.
P. Loridan, J. Morgan, 𝜖-regularized two-level optimization problems: approximation and existence results, in Optimization-Fifth French-German Conference Castel Novel 1988. Lecture Notes in Mathematics, vol. 1405 (Springer, Berlin, 1989), pp. 99–113
37.
P. Loridan, J. Morgan, New results on approximate solution in two-level optimization. Optimization 20(6), 819–836 (1989)
38.
P. Loridan, J. Morgan, Weak via strong Stackelberg problem: new results. J. Glob. Optim. 8, 263–287 (1996)
39.
L. Lozano, J.C. Smith, A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65(3), 768–786 (2017)
40.
J. Lu, C. Shi, G. Zhang, On bilevel multi-follower decision making: general framework and solutions. Inf. Sci. 176(11), 1607–1627 (2006)
41.
J. Lu, G. Zhang, J. Montero, L. Garmendia, Multifollower trilevel decision making models and system. IEEE Trans. Ind. Inf. 8(4), 974–985 (2012)
42.
J. Lu, J. Han, Y. Hu, G. Zhang, Multilevel decision-making: a survey. Inf. Sci. 346–347, 463–487 (2016)
43.
R. Lucchetti, F. Mignanego, G. Pieri, Existence theorems of equilibrium points in Stackelberg games with constraints. Optimization 18, 857–866 (1987)
44.
A.V. Malyshev, A.S. Strekalovskii, Global search for pessimistic solution in bilevel problems, in Proceedings of the Toulouse Global Optimization Workshop, ed. by S. Cafieri, B.G. Toth, E.M.T. Hendrix, L. Liberti, F. Messine (2010), pp. 77–80
45.
A. Marhfour, Mixed solutions for weak Stackelberg problems: existence and stability results. J. Optim. Theory Appl. 105, 417–440 (2000)
46.
M. Sakawa, I. Nishizaki, Cooperative and Noncooperative Multi-level Programming (Springer Science and Business Media, Berlin/Heidelberg, 2009)
47.
M. Sakawa, I. Nishizaki, Interactive fuzzy programming for multi-level programming problems: a review. Int. J. Multicrit. Decis. Making 2, 241–266 (2012)
48.
A. Sinha, P. Malo, K. Deb, Evolutionary bilevel optimization: an introduction and recent advances, in Recent Advances in Evolutionary Multi-objective Optimization (Springer International Publishing, Cham, 2017), pp. 71–103
49.
A. Sinha, P. Malo, K. Deb, A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Trans. Evol. Comput. 22(2), 276–295 (2018)
50.
H.V. Stackelberg, The Theory of Market Economy (Oxford University Press, Oxford, 1952)
51.
A. Tsoukalas, W. Wiesemann, B. Rustem, Global Optimisation of Pessimistic Bi-level Problems, ed. by P.M. Pardalos, T.F. Coleman. Lectures on Global Optimization. Fields Institute Communications, vol. 55 (American Mathematical Society, Providence, RI, 2009), pp. 215–243
52.
L. Vicente, P. Calamai, Bilevel and multilevel programming: a bibliography review. J. Global Optim. 5, 291–306 (1994)
53.
U.P. Wen, S.T. Hsu, Linear bi-level programming problems-a review. J. Oper. Res. Soc. 42(2), 125–133 (1991)
54.
W. Wiesemann, A. Tsoukalas, P. Kleniati, B. Rustem, Pessimistic bi-level optimisation. SIAM J. Optim. 23, 353–380 (2013)
55.
R.K. Wood, Bilevel Network Interdiction Models: Formulations and Solutions. Wiley Encyclopedia of Operations Research and Management Science (Wiley, Hoboken, 2011)
56.
B. Zeng, Easier than we thought-a practical scheme to compute pessimistic bilevel optimization problem. Technical report, University of Pittsburgh (2015) Available via optimization-online.org
57.
G. Zhang, J. Lu, Y. Gao, Multi-Level Decision Making: Models, Methods and Applications (Springer, Berlin, 2015)
58.
G. Zhang, J. Han, J. Lu, Fuzzy bi-level decision-making techniques: a survey. Int. J. Comput. Intell. Syst. 9, 25–34 (2016)
59.
Y. Zheng, Z. Wan, K. Sun, T. Zhang, An exact penalty method for weak linear bilevel programming problem. J. Appl. Math. Comput. 42, 41–49 (2013)
60.
Y. Zheng, D. Fang, Z. Wan, A solution approach to the weak linear bilevel programming problems. Optimization 7, 1437–1449 (2016)
61.
Y. Zheng, G. Zhang, J. Han, J. Lu, Pessimistic bilevel optimization model for risk-averse production-distribution planning. Inf. Sci. 372 , 677–689 (2016)
62.
Y. Zheng, Z. Zhu, L. Yuan, Partially-shared pessimistic bilevel multi-follower programming: concept, algorithm, and application. J. Inequal. Appl. 2016, 1–13 (2016)
63.
Y. Zheng, X. Zhuo, J. Chen, Maximum entropy approach for sloving pessimistic bilevel programming problems. Wuhan Univ. J. Nat. Sci. 1, 63–67 (2017)
64.
Y. Zheng, G. Zhang, Z. Zhang, J. Lu, A reducibility method for the weak linear bilevel programming problems and a case study in principal-agent. Inf. Sci. 454, 46–58 (2018)