Definition 1:

For the upper-level objective function F : Rn×Rm→R and lower-level objective function f : Rn×Rm→R , the bilevel problem is given by

View Source\begin{align*} \mathop {{\mathrm {``} {\mathrm {min}} {\text{''}}}}\limits _{x_{u}\in X_{U},x_{l}\in X_{L}}&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}&\\ x_{l}\in \mathop{\textrm {argmin}}\limits _{x_{l} \in X_{L}}&\lbrace f(x_{u},x_{l})\,:\,g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J \rbrace \\&~G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K \end{align*}

An equivalent formulation of the above problem can be stated in terms of set-valued mapping (multivalued function) as follows.

Definition 2:

Let Ψ : Rn⇉Rm be a set-valued mapping

View Source\begin{equation*} \Psi (x_{u})= \mathop{\textrm {argmin}}\limits _{x_{l} \in X_{L}}\left \{{\,f(x_{u},x_{l})~:~g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J}\right \} \end{equation*}

minxu∈XU,xl∈XL  subject to  F(xu,xl)xl∈Ψ(xu)Gk(xu,xl)≤0,k=1,…,K

View Source\begin{align*} \mathop {\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}}~~&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}~~&x_{l} \in \Psi (x_{u}) \\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K \end{align*}

In the above two definitions, quotes have been used while specifying the upper level minimization problem because of an ambiguity that arises in case of multiple lower level optimal solutions for any given upper level decision vector. In the presence of multiple lower level optimal solutions there is lack of clarity at the upper level as to which optimal solution from the lower level should be utilized. This ambiguity can be sorted by defining different positions that may be assumed by the leader. The two common positions that have been widely studied are optimistic (weak) position and pessimistic (strong) position, which we discuss next.

A. Optimistic Position

In an optimistic position, in the presence of multiple lower level optimal solutions, the leader expects the follower to choose that solution from the optimal set Ψo(xu) , which leads to the best objective function value at the upper level. The choice function of the follower in this case may be defined as follows:

View Source\begin{equation*} \Psi ^{o}(x_{u}) = \mathop{\textrm {argmin}}\limits _{x_{l} \in X_{L}}\left \{{F(x_{u},x_{l})~:~x_{l} \in \Psi (x_{u})}\right \}. \end{equation*}

minxu∈XU,xl∈XLsubject toF(xu,xl)xl=Ψo(xu)Gk(xu,xl)≤0,k=1,…,K.

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}}\quad&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}\quad&x_{l} = \Psi ^{o}(x_{u}) \\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K. \end{align*}

Optimistic position is more tractable as compared to the pessimistic position; therefore, most of the studies handle optimistic version of the bilevel optimization problem. The optimistic formulation is guaranteed to have an optimal solutions under reasonable assumptions of regularity and compactness that are stated in the theorem below.

B. Pessimistic Position

In a pessimistic position, in the presence of multiple lower level optimal solutions, the leader optimizes for the worst case, i.e., she assumes that the follower may choose that solution from the optimal set which leads to the worst objective function value at the upper level. Such a worst case choice function of the follower may be defined as

View Source\begin{equation*} \Psi ^{p}(x_{u}) = \mathop{\textrm {argmax}}\limits _{x_{l}}\left \{{F(x_{u},x_{l})~:~x_{l} \in \Psi (x_{u})}\right \}. \end{equation*}

minxu∈XU,xl∈XLsubject toF(xu,xl)xl=Ψp(xu)Gk(xu,xl)≤0,k=1,…,K.

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}}\quad&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}\quad&x_{l} = \Psi ^{p}(x_{u}) \\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K. \end{align*}

C. Example

Below we provide a simple example of a bilevel optimization problem [71] that arises in case of two firms in a Stackelberg competition. The leader has complete knowledge about the follower’s inverse-demand function and the cost function, and desires to maximize it’s own profits by taking into account the actions of the follower firm. The two firms compete solely by choosing their production levels that maximize their profits (Πl and Πf ), and the follower acts only after observing the actions of the leader. Formally, this model can be presented as follows:

View Source\begin{align} \max _{q_{l},q_{f}}&\Pi _{l} = P(q_{l},q_{f}) q_{l} - C_{l}(q_{l}) \\ \mbox {s.t.}&~q_{f} \in \mathop{\textrm {argmax}}\limits _{q_{f}} \lbrace {\Pi _{f} = P(q_{l},q_{f}) q_{f} - C_{f}(q_{f})} \rbrace \\&q_{l}, q_{f} \geq 0 \end{align}

By assuming that the firms produce and sell homogeneous goods, we may assume a single linear price function for both firms as an inverse demand function of the form

View Source\begin{equation} P(q_{l},q_{f}) = \alpha - \beta (q_{l},q_{f}) \end{equation}

C(ql)=C(qf)=δlq2l+γlql+clδfq2f+γfqf+cf(5)(6)

View Source\begin{align} C(q_{l})=&\delta _{l} q_{l}^{2} + \gamma _{l} q_{l} + c_{l} \\ C(q_{f})=&\delta _{f} q_{f}^{2} + \gamma _{f} q_{f} + c_{f} \end{align}

The optimal level of production of the leader (q∗l) and the follower (q∗f) in terms of the constants of the model is given as follows:

View Source\begin{align} q_{l}^{*}=&\frac {2\left ({\beta + \delta _{f}}\right )\left ({\alpha - \gamma _{l}}\right ) - \beta \left ({\alpha - \gamma _{f}}\right )}{4\left ({\beta + \delta _{f}}\right )\left ({\beta + \delta _{l}}\right ) - 2\beta ^{2}} \\ q_{f}^{*}=&\frac {\alpha - \gamma _{f}}{2\left ({\beta + \delta _{f}}\right )} - \frac {\beta \left ({\alpha - \gamma _{l}}\right )-{ \frac {\beta ^{2}\left ({\alpha - \gamma _{f}}\right )}{2\left ({\beta + \delta _{f}}\right )}}}{4\left ({\beta + \delta _{f}}\right )\left ({\beta + \delta _{l}}\right ) - 2\beta ^{2}}. \end{align}

A. Single-Level Reduction

When the lower level problem is convex and sufficiently regular, it is possible to replace the lower level optimization problem with its Karush-Kuhn–Tucker (KKT) conditions. The KKT conditions appear as Lagrangian and complementarity constraints, and reduce the overall bilevel optimization problem to a single-level constrained optimization problem. For example, the problem in Definition 1 can be reduced to the following form, when the convexity and regularity conditions at the lower level are met:

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}, \lambda }\quad&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}\quad&\\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K\\&\nabla _{x_{l}} L(x_{u},x_{l},\lambda ) = 0\\&g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J\\&\lambda _{j} g_{j}(x_{u},x_{l}) = 0, j=1,\ldots ,J\\&\lambda _{j} \geq 0, j=1,\ldots ,J \end{align*}

L(xu,xl,λ)=f(xu,xl)+∑j=1Jλjgj(xu,xl).

View Source\begin{equation*} L(x_{u},x_{l},\lambda ) = f(x_{u},x_{l}) + \sum _{j=1}^{J} \lambda _{j} g_{j}(x_{u},x_{l}). \end{equation*}

Interestingly, for linear bilevel optimization problems, the Lagrangian constraint is also linear. Therefore, the single-level optimization problem is a mixed integer linear program. Approaches based on vertex enumeration [25], [45], [161], as well as branch-and-bound (B&B) [16], [70] have been used to solve these problems. It is noteworthy that B&B methods constitute an exponentially slow algorithm with the number of integer variables. But, B&B approaches have been successfully applied to single-level reductions of linear-quadratic [17] and quadratic-quadratic [5], [64] bilevel problems. An extended KKT approach has also been considered [138] for handling linear bilevel problems.

B. Descent Methods

In addition to KKT-based approaches, a number of descent methods have been proposed for solving bilevel optimization problems. A descent direction in bilevel optimization leads to decrease in upper level function value while keeping the new point feasible. Given that a point is considered feasible only if it is lower level optimal, finding the descent direction can be quite challenging. To resolve the problem, researchers have investigated ways to approximate the gradient of the upper level objective [95] as well as considered formulation of auxiliary programs [136], [165] to determine the direction of descent.

C. Penalty Function Methods

In penalty function methods the bilevel optimization problem is handled by solving a series of unconstrained optimization problems. The unconstrained problem is generated by adding a penalty term that measures the extent of violation of the constraints. The penalty term often requires a parameter and takes the value zero for feasible points and positive (minimization) for infeasible points. For bilevel problems, the first attempt toward using a penalized approach was made by Aiyoshi and Shimizu [1], [2]. They replaced the lower level problem by a penalized problem; however, the bilevel hierarchy was still maintained and the reduced problem was still difficult to solve. Later double penalty method was introduced in [84], where both upper and lower level objective functions were penalized. The problem was reduced into a single level task by replacing the penalized lower level problem with its KKT conditions, and then solving the single level formulation by penalization. In a number of studies, the lower level problem is directly replaced by its KKT conditions and then a penalized approach is used to solve the single level problem. Few studies where penalty function approach has been used for linear bilevel problems are [112] and [175]. White and Anandalingam [175] converted the linear bilevel program into a penalized bilinear optimization problem, and then solve a series of bilinear problems to find the optimum. Lv et al.. [112] reduced the linear bilevel program into single level using KKT conditions, and then append the complementary slackness condition to the upper level objective function with a penalty. The penalized problem is then handled using a series of linear programs.

D. Trust-Region Methods

In trust-region methods, the algorithms approximate a certain region of the objective function with a model function. The region is expanded if the approximation is good, otherwise it is contracted. The first study using trust-region method to solve nonlinear bilevel programs was presented in [108], where the lower level problem had a convex objective function and linear constraints. However, no upper level constraints were considered. Later, a more general idea was proposed in [116], where the authors locally approximate the bilevel program with a model involving a linear program at the upper level and a linear variational inequality at the lower level. Trust-region and line search ideas have been combined to approach the bilevel optimum over iterations. Similarly, Colson et al. [50] approximated the bilevel program around an iterate with a model that itself is a linear-quadratic bilevel program. The authors proposed to solve the linear-quadratic bilevel program using a mixed integer solver after reducing it to a single level problem using its lower level KKT conditions. Convergence is achieved by sequentially solving linear-quadratic bilevel models.

Next, we discuss about evolutionary algorithms for bilevel optimization. At this point, we would like to refer the readers to other review papers [49], [57], [90], [150], [164] and books [18], [60], [61], [140], [159] on bilevel optimization.

A. Nested Methods

Nested evolutionary algorithms are a popular approach to handle bilevel problems, where lower level optimization problem is solved corresponding to each and every upper level member [153]. Though effective, nested strategies are computationally very expensive and not viable for large scale bilevel problems. Nested methods in the area of evolutionary algorithms have been used in primarily two ways. The first approach has been to use an evolutionary algorithm at the upper level and a classical algorithm at the lower level, while the second approach has been to utilize evolutionary algorithms at both levels. Of course, the choice between two approaches is determined by the complexity of the lower level optimization problem.

One of the first evolutionary algorithms for solving bilevel optimization problems was proposed in the early 1990s. Mathieu et al. [118] used a nested approach with genetic algorithm at the upper level, and linear programming at the lower level. Another nested approach was proposed in [184], where the upper level was an evolutionary algorithm and the lower level was solved using Frank-Wolfe algorithm (reduced gradient method) for every upper level member. The authors demonstrated that the idea can be effectively utilized to solve nonconvex bilevel optimization problems.

Nested particle swarm optimization (PSO) was used in [103] to solve bilevel optimization problems. The effectiveness of the technique was shown on a number of standard test problems with small number of variables, but the computational expense of the nested procedure was not reported. A hybrid approach was proposed in [102], where simplex-based crossover strategy was used at the upper level, and the lower level was solved using one of the classical approaches. The authors report the generations and population sizes required by the algorithm that can be used to compute the upper level function evaluations, but they do not explicitly report the total number of lower level function evaluations, which presumably is high.

Differential evolution (DE) based approaches have also been used, for instance, Zhu et al. [188] used DE at the upper level and relied on the interior point algorithm at the lower level; similarly, Angelo et al. [11] have used DE at both levels. Authors have also combined two different specialized evolutionary algorithms to handle the two levels, for example, Angelo and Barbosa [12] used an ant colony optimization to handle the upper level and DE to handle the lower level in a transportation routing problem. Another nested approach utilizing ant colony algorithm for solving a bilevel model for production-distribution planning is [36]. Scatter search algorithms have also been employed for solving production-distribution planning problems, for instance [39].

Through a number of approaches involving evolutionary algorithms at one or both levels, the authors have demonstrated the ability of their methods in solving problems that might otherwise be difficult to handle using classical bilevel approaches. However, as already stated, most of these approaches are practically nonscalable. With increasing number of upper level variables, the number of lower level optimization tasks required to be solved increases exponentially. Moreover, if the lower level optimization problem itself is difficult to solve, numerous instances of such a problem cannot be solved, as required by these methods.

B. Single-Level Reduction

The idea behind single-level reduction, in the context of evolutionary algorithms, is similar to the discussion in Section III-A. A number of researchers in the area of evolutionary computation have also used the KKT conditions of the lower level to reduce the bilevel problem into a single-level problem. Most often, such an approach is able to solve problems that adhere to certain regularity conditions at the lower level because of the requirement of the KKT conditions. However, as the reduced single-level problem is solved with an evolutionary algorithm, usually the upper level objective function and constraints can be more general and not adhering to such regularities. For instance, one of the earliest papers using such an approach is by Hejazi et al. [82], who reduced the linear bilevel problem to single-level and then used a genetic algorithm, where chromosomes emulate the vertex points, to solve the problem. Wang et al. [171] reduced the bilevel problem into a single-level optimization problem using KKT conditions, and then utilized a constraint handling scheme to successfully solve a number of standard test problems. Their algorithm was able to handle nondifferentiability at the upper level objective function, but not elsewhere. Later on, Wang et al. [172] introduced an improved algorithm that was able to handle nonconvex lower level problem and performed better than the previous approach [171]. However, the number of function evaluations in both approaches remained quite high (requiring function evaluations to the tune of 100 000 for 2–5 variable bilevel problems). Wang et al. [169] used a simplex-based genetic algorithm to solve linear-quadratic bilevel problems after reducing it to a single level task. More recently, Jiang et al. [86] reduced the bilevel optimization problem into a nonlinear optimization problem with complementarity constraints, which is sequentially smoothed and solved with a PSO algorithm. Along similar lines of using lower level optimality conditions, Li [101] solved a fractional bilevel optimization problem by utilizing optimality results of the linear fractional lower level problem. Wan et al. [167] embedded the chaos search technique in PSO to solve single-level reduced problem.

C. Metamodeling-Based Methods

Metamodeling-based solution methods are commonly used for optimization problems [168], where actual function evaluations are expensive. A meta-model or surrogate model is an approximation of the actual model that is relatively quicker to evaluate. Based on a small sample from the actual model, a surrogate model can be trained and used subsequently for optimization. Given that, for complex problems, it is hard to approximate the entire model with a small set of sample points, researchers often resort to iterative meta modeling techniques, where the actual model is approximated locally during iterations.

Bilevel optimization problems contain an inherent complexity that leads to a requirement of large number of evaluations to solve the problem. Metamodeling, when used with population-based algorithms, offers a viable means to handle bilevel optimization problems. In this section, we discuss four ways in which metamodeling can be applied to bilevel optimization. The discussion related to approximation of the rational reaction set and lower level optimal value function is a review of some recent work. However, before starting, we refer the readers to Fig. 3, which provides an understanding of these two mappings graphically for a hypothetical bilevel problem. We also provide a brief discussion on approximating the bilevel problem with an auxiliary problem.

Fig. 3.

Graphical representation of rational reaction set (Ψ ) and lower level optimal value function (φ ).

Show All

1) Reaction Set Mapping:

One of the approaches to solve bilevel optimization problems using evolutionary algorithms would be through iterative approximation of the reaction set mapping Ψ . If the Ψ -mapping (introduced in Table I) in a bilevel optimization problem is known, it effectively reduces the problem to single level optimization. However, this mapping is seldom available; therefore, the approach could be to solve the lower level problem for a few upper level members and then utilize the lower level optimal solutions and corresponding upper level members to generate an approximate mapping Ψ^ . It is noteworthy that approximating a set-valued Ψ -mapping offers its own challenges and is not a straightforward task. Assuming that an approximate mapping, Ψ^ , can be generated, the following single level optimization problem can be solved for a few generations of the algorithm before deciding to further refine the reaction set:

minxu∈XU,xl∈XLsubject toF(xu,xl)xl∈Ψ^(xu)Gk(xu,xl)≤0,k=1,…,K.

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}}&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}\quad&\\&x_{l} \in \hat {\Psi }(x_{u}) \\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K. \end{align*} Evolutionary algorithms that rely on this idea to solve bilevel optimization problems are [13], [144], [145], and [149]. Sinha et al. [144], [145] have used quadratic approximation to approximate the local reaction set. This helps in saving lower level optimization calls when the approximation for the local reaction set is good. In case the approximations generated by the algorithm are not acceptable, the method defaults to a nested approach. It is noteworthy that a bilevel algorithm that uses a surrogate model for reaction set mapping may need not be limited to quadratic models but other models can also be used.

2) Optimal Lower Level Value Function:

Another way to use metamodeling would be through the approximation of the optimal value function φ . If the φ -mapping (introduced in Table I) is known, the bilevel problem can once again be reduced to single level optimization problem as follows [183]:

minxu∈XU,xl∈XLsubject toF(xu,xl)f(xu,xl)≤φ(xu)gj(xu,xl)≤0,j=1,…,JGk(xu,xl)≤0,k=1,…,K.

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}}\quad&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}\quad&f(x_{u},x_{l}) \le \varphi (x_{u}) \\&g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J\\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K. \end{align*} However, since the value function is seldom known, one can attempt to approximate this function using metamodeling techniques. The optimal value function is a single-valued mapping; therefore, approximating this function avoids the complexities associated with set-valued mapping. As described previously, an approximate mapping φ^ , can be generated with the population members of an evolutionary algorithm and the following single level optimization problem can be solved with refinements at every few generations:

minxu∈XU,xl∈XL  subject to  F(xu,xl)f(xu,xl)≤φ^(xu)gj(xu,xl)≤0,j=1,…,JGk(xu,xl)≤0,k=1,…,K.

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}, x_{l}\in X_{L}}~~&F(x_{u},x_{l}) \\ \mathop{\textrm {subject to}}~~&f(x_{u},x_{l}) \le \hat {\varphi }(x_{u}) \\&g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J\\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K. \end{align*} An evolutionary approach that relies on this idea can be found in [143] and [148].

3) Bypassing Lower Level Problem:

Another way to use a meta-model in bilevel optimization would be completely by-pass the lower level problem, as follows:

minxu∈XU  subject to  F^(xu)G^k(xu)≤0,k=1,…,K.

View Source\begin{align*} \mathop{\textrm {min}}\limits _{x_{u}\in X_{U}}~~&\hat {F}(x_{u}) \\ \mathop{\textrm {subject to}}~~&\hat {G}_{k}(x_{u})\leq 0, k=1,\ldots ,K. \end{align*} Given that the optimal xl are essentially a function of xu , it is possible to construct a single level problem by ignoring xl completely. However, the landscape for such a single level problem can be highly nonconvex, disconnected and nondifferentiable. Advanced metamodeling techniques might be required to use this approach, which may be beneficial for certain classes of bilevel problems. A training set for the meta-model can be constructed by solving few lower level problems for different xu . Both upper level objective F and constraint set (Gk ) can then be meta-modeled using xu alone. Given the complex structure of such a single-level problem, it might be sensible to create such an approximation locally. We are currently pursuing such an approach using artificial neural network as the metamodeling approach.

A. Discrete Bilevel Optimization Survey

One of the early works on discrete bilevel optimization was by Vicente et al. [166], which focused on discrete linear bilevel programs, and analyzed the properties and existence of the optimal solution for different kinds of discretizations arising from the upper and lower level variables. The authors have shown in this paper that certain compactness conditions guarantee the existence of optimal solution in continuous-continuous linear bilevel programs, discrete-continuous linear bilevel programs, and discrete-discrete linear bilevel programs. The conditions are equivalent to stating that the inducible region is nonempty. However, the existence conditions in the case of continuous-discrete linear bilevel programs are not straightforward. For instance, the inducible region for the continuous-discrete linear bilevel problem in Fig. 4 is a noncompact set that may lead to nonexistence of a bilevel optimal solution even when the inducible region is nonempty.

A few studies preceded the study by Vicente et al. [166]. For instance, Moore and Bard [123] solved mixed integer linear bilevel problems. The authors pointed out the difficulties involved in fathoming while solving mixed integer bilevel problems using traditional B&B techniques. Certain fathoming rules used in case of mixed integer linear programming, like fathoming when the relaxed subproblem is worse than the value of the incumbent or fathoming when the solution of the relaxed subproblem is feasible for the mixed integer problem, are not directly applicable to mixed integer linear bilevel problems. Therefore, the authors proposed a B&B approach involving stricter fathoming conditions. However, the algorithm has a nested structure and is not scalable beyond few integer variables, and to counter which the authors also proposed some heuristics. This paper was followed by [19], where the same authors solved discrete linear bilevel programs involving only binary variables using an implicit enumeration scheme. In this approach, the authors place a cut, similar to the one used by Bialas and Karwan [25] (for the continuous linear bilevel program), seeking incremental improvements in the upper level objective function. A cutting plane method utilizing the Chvátal-Gomory cut for the continuous-discrete bilevel program was proposed in [59]. Benders-decomposition-based techniques have also been employed to solve bilevel problems with mixed integers at the upper level and continuous linear programs at the lower level. The original problem is decomposed into a master and a slave problem. Fixing the integer values converts the slave problem into a bilevel linear program which is solved by KKT-based reduction techniques, and the solution to the slave is utilized to create a cut for the master problem. The algorithm switches between master and slave problems until the optimality criteria is met. Certain studies in this direction are [40], [69], and [135].

Despite the attempts made toward algorithm development for discrete bilevel programs, the research is still open for new methods and ideas as none of the proposed techniques would scale well for problems with larger number of variables. Apart from a few nested approaches and KKT-based single level reduction approaches, to our best knowledge, there does not exist any algorithmic study involving evolutionary algorithms for mixed integer bilevel problems that attempt to solve the problem efficiently by utilizing its properties. However, given that the evolutionary approaches are, in particular, potent for handling difficulties such as discreteness and nondifferentiabilities they offer a significant scope for solving discrete bilevel optimization problems. Some attempts toward mixed integer bilevel optimization using evolutionary methods are [4], [14], [37], [43], [78], [81], [100], and [120].

There is no dearth of application problems involving discrete variables. While mixed integer bilevel problems are ubiquitous, even combinatorial bilevel programs find innumerable applications in the areas of network design, facility location, hub-and-spoke networks, etc. In these areas, these problems are commonly studied in the context of interdiction, protection, robust design, competition and supply chain management, among others. Some of the related applications are highlighted in Section VII.

Definition 3:

For the upper-level objective function F : Rn×Rm→Rp and lower-level objective function f : Rn×Rm→Rq , the multiobjective bilevel problem is given by

View Source\begin{align*} \mathop {\textrm {min}}\limits _{x_{u}\in X_{U},x_{l}\in X_{L}}&F(x_{u},x_{l}) = \left ({F_{1}(x_{u},x_{l}),\ldots ,F_{p}(x_{u},x_{l})}\right ) \\ \mathop{\textrm {subject to}}&\\&x_{l}\in \mathop{\textrm {argmin}}\limits _{x_{l} \in X_{L}} \lbrace f(x_{u},x_{l}) = (\,f_{1}(x_{u},x_{l}),\ldots ,f_{q}(x_{u},x_{l})): \\&g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J \rbrace \\&G_{k}(x_{u},x_{l})\leq 0, k=1,\ldots ,K \end{align*}

The set-valued mapping in this case can be defined as follows and an equivalent definition can be written as in the single-objective case:

View Source\begin{align*} \Psi (x_{u})=&\mathop{\textrm {argmin}}\limits _{x_{l} \in X_{L}}\Biggl \{{\,f(x_{u},x_{l}) = \left ({\,f_{1}(x_{u},x_{l}),\ldots ,f_{q}(x_{u},x_{l})}\right )~:} \\&{ g_{j}(x_{u},x_{l})\leq 0, j=1,\ldots ,J}\Biggr \}. \end{align*}

A. Optimistic Versus Pessimistic

The optimistic or pessimistic position becomes more prominent in multiobjective bilevel optimization. In the presence of multiple objectives at the lower level, the set-valued mapping Ψ(⋅) normally represents a set of Pareto-optimal (PO) solutions corresponding to any given xu , which we refer as follower’s PO frontier. A solution to the overall problem (with optimistic or pessimistic position) is expected to produce a tradeoff frontier for the leader that we refer as the leader’s PO frontier. From the perspective of the leader, it becomes important that what kind of position she seeks to take while solving the problem, as it determines that which solution(s) from the lower level frontier should be considered at the upper level.

Though optimistic positions have commonly been studied in classical [66] and evolutionary [56] literature in the context of multiobjective bilevel optimization; it is far from realism to expect that the follower will cooperate to an extent that she chooses any point from her PO frontier that is most suitable for the leader. This relies on the assumption that the follower is indifferent to the entire set of optimal solutions, and therefore decides to cooperate. The situation was entirely different in the single-objective case, where, in case of multiple optimal solutions, all the solutions offered an equal value to the follower. However, this cannot be assumed in the multiobjective case. Solution to the optimistic formulation in multiobjective bilevel optimization leads to the best possible PO frontier that can be achieved by the leader. Similarly, solution to the pessimistic formulation leads to the worst possible PO frontier at the upper level.

If the value function or the choice function of the follower is known to the leader, it provides an information as to what kind of tradeoff is preferred by the follower. A knowledge of such a function effectively, casually speaking, reduces the lower level optimization problem into a single-objective optimization task, where the value function may be directly optimized. The leader’s PO frontier for such intermediate positions lies between the optimistic and the pessimistic frontiers. Fig. 5 shows the optimistic and pessimistic frontiers for a hypothetical multiobjective bilevel problem with two objectives at upper and lower levels. Follower’s frontier corresponding to x1u , x2u , and x3u , and her decisions Al , Bl , and Cl are shown in the insets. The corresponding representations of the follower’s frontier and decisions (Au , Bu , and Cu ) in the leader’s space are also shown.

Fig. 5.

Leader’s PO frontiers for optimistic and pessimistic positions. Few follower’s PO frontiers are shown (in insets) along with their representations in the leader’s objective space.

Show All

B. Example

Below, we provide a bilevel optimization problem involving design of a tax policy [152]. The upper level in this example is the government that wants to tax the lower level, a mining company, based on the pollution it causes to the environment. The government here has two objectives: the first objective is to maximize the revenues generated by the mining project, which may include the additional jobs, taxes, etc.; and the second objective is to minimize the harm caused to the environment as a result of mining. Obviously, there is a tradeoff between the two objectives, and the government as a decision maker needs to choose one of the preferred tradeoff solutions. The mining company has a sole objective of maximizing its profit under the constraints set by the government. In this scenario, the government would like to have a tax structure such that it is able to maximize its own revenues in addition to being able to restrain the mining company from causing extensive damage to the environment. It is possible for the leader to optimally regulate the problem in its favor, provided that it has complete knowledge of the follower’s strategies. The hierarchical optimization problem in this case can be formulated as follows:

View Source\begin{align} \max _{\tau ,q}&~{\textstyle \mathbf {F}}(q, \tau ) = (R, - D) \\ \mbox {s.t.} \quad&q \in \mathop{\textrm {argmax}}\limits _{q} \left \{{\begin{array}{lllll} \pi (q)&=& p(q)q - c(q) - R\\ \pi (q)&\ge & 0 \\ \end{array}}\right \} \\&q \ge 0, \tau \ge 0. \end{align}

In (9), the first objective deals with the tax revenue, where R=τq ; τ is the per unit tax imposed on the mine, and q is the amount of metal extracted from the ore by the follower. The second objective denotes the environmental damage caused by the mine that the government ultimately wants to minimize. D=kq , where k is the pollution coefficient signifying the negative impact of extraction on the environment. The damages are thus linear and scale proportionately with the amount of gold extracted from the earth since a larger base of operation implies larger environmental damage.

Equation (10) gives the profit of the mine, where p(q)q (price function times amount of metal extracted) is the revenue function, and c(q) is the extraction cost function followed by the additional tax levied on the mine. The mine is most likely to be a price taker when it comes to the price of gold and must base its mining decisions on the possible price paid by their customers. It would therefore be plausible to replace the price function for gold in the above equation by a constant. However, given the assumption that the mine can extract a large amount of ore, and subsequently gold, at one time, it might be possible for it to affect the price of gold slightly. Therefore, we assume the price function to be linear with a small slope. Extraction cost can be considered to be quadratic. Thus, we have the following model: