Project topics and materials
Get Complete Project Material File(s) Now! »
Bilevel programming
Bilevel programming is a eld of mathematical programming in which some variables are constrained to be the optimal solution of another optimization problem. Therefore, bilevel optimization can be used to model the real-world hierarchical relationship between two autonomous, and possibly con ictual, decision makers. In this chapter, we discuss the key concepts of bilevel optimization. In Section 1.1, we introduce the basic concepts of bilevel optimization. We present some of the well-known single-level reformulation approaches in Section 1.2. In Section 1.3, some solution methods for the bilevel problems are described.
In the following, given a formulation pPq of an optimization problem, we use the term reformulation to describe a formulation having the same set of optima of pPq, i.e., what is de ned as exact reformulation in [131, De nition 10]. With the term relaxation, we refer to a formulation having a feasible set which contains the feasible set of pPq [131, De nition 13]. Finally, we use the term restriction when referring to a formulation having a feasible set which is included in the feasible set of pPq.
Introduction
From a historical point of view, bilevel optimization is closely related to the economic problem of Stackelberg (1934) in the eld of game theory [196, 197], which was used to model the interaction among two rms competing sequentially on the quantity of output they produce of a homogeneous good. A formal de nition of bilevel programming problems was rst introduced by Bracken and McGill (1973) [46] as \mathematical programs with optimization problems in the constraints », but the designation bilevel and multilevel were only later introduced by Candler and Norton (1977) [52]. For a general overview of bilevel programming, we refer to the thorough surveys [195, 65, 74, 73], and to the books by Bard [27] and Dempe [72, 77].
A bilevel programming problem can be seen as a hierarchical game, where two players (a leader and a follower) make their decisions following a hierarchical order. Firstly, the leader makes his/her choice and communicates this to the follower, who will select a response taking into account the selection of the leader, and give it back to the leader. Thus, the leader’s task is to determine the best decision optimizing, together with the reaction of the follower, his/her own objective function. Most of the literature on bilevel programming consider the optimistic problem. One of the reasons can be that this problem has an optimal solution under quite reasonable assumptions (see [72]). When cooperation of the leader and the follower is not allowed, or if the leader wants to bound the \damage » resulting from an undesirable selection by the follower, the pessimistic approach [203, 135] must be used: the leader assumes that the follower selects the optimal solution corresponding to the worst upper-level objective function value. To model this, the leader minimizes the function max F px; yq over x.
Single-level reformulations
To investigate bilevel problems, their transformation into one-level optimization problems may be necessary, and di erent approaches can be used towards this aim [75]. First of all, instead of using the point-to-set mapping, linking the leader’s selection to the set of optimal solutions of the follower’s problem, one can also use the value function ’pxq mintfpx; yq | gpx; yq ⁄ 0u; (1.14)
which is the so-called value function reformulation. Problems (1.6){(1.9) and (1.15){(1.19) are equivalent (both w.r.t. local and global optima). The function ’pxq is in general not di erentiable, even if all the constraints and the objective function in the lower level are smooth [76]. Using nonsmooth analysis, optimality conditions for the optimal value transformation can be obtained (see, e.g., [76]).
When the lower-level problem is convex for each feasible upper-level variable, and satis es some regularity conditions (e.g., Slater’s constraint quali cation), it is possible to reformulate the bilevel problem into a single-level problem using either KKT conditions of the lower level or strong duality applied to the lower-level problem. Indeed, in this case, the lower-level problem can be replaced by its necessary and su cient KKT conditions where P Rl is the Lagrangian multiplier associated to the lower-level convex inequality constraint gpx; yq ⁄ 0: Eq. (1.22) (setting the gradient of the lower-level Lagrangian function equal to zero) corresponds to lower-level stationarity conditions, Eq. (1.23) to lower-level primal and dual feasibility, and Eq. (1.24) to complementarity slackness. If the lower level is nonconvex, the formulation (1.20){ (1.25) is a relaxation of the original bilevel problem, since the set of bilevel feasible solutions is enlarged by adding local optima as well as stationary solutions of the lower-level problem to it.
We can claim that the above presented reformulation is the most often used approach to deal with bilevel problems, despite the nonconvexities that occur in the complementarity constraint (1.24). Indeed, problem (1.20){(1.25) is a Mathematical Problem with Complementarity Constraints (MPCC) [139, 157]. In [178], it is shown that the Mangasarian-Fromovitz constraint quali cation is violated at every feasible point of the problem (1.20){(1.25). Thus, the solution of the problem and also the de nition of (necessary and su cient) optimality conditions is di cult.
For bilevel problems with convex lower level, another approach consists in exploiting strong duality of such lower level. Given the lower level mintfpx; yq | y P Fpx; yqu
Solution approaches
In this section we introduce the main methods from the literature to tackle bilevel problems, following the structure of surveys [65, 180, 123, 194]. Being bilevel programming problems inherently complex (see Chapter 2), it is not surprising that most algorithmic literature has focused on the simplest case of the continuous Bilevel Linear Problems (BLPs) having only continuous variables and linear functions in both the levels [33].
There may be context-speci c ways to choose a safe value for big-Ms, but this is not always the case. In [124], it is proved that nding a correct big-M cannot be done e ciently, i.e., in polynomial-time, unless P NP. If the selected big-Ms is too small, the solution of the MILP problem could be not bilevel optimal. Otherwise, the choice of too large big-Ms can lead to weak relaxations, which, in turn, may make the model hard for the solvers.
Several branch-and-bound approaches exploit the complementarity between the multipliers and the slack variables of the lower-level constraints in the condition (1.24). This is discussed in [28] and [94], where a general branch-and-bound method is applied to the KKT reformulation of a BLP. The approach was adapted to linear-quadratic in [29] and to quadratic-quadratic bilevel problems in [16, 26, 86], with some additional assumptions.
Novel branching rules, di erent from most-violated complementarity, to solve medium-size BLPs have been studied in [109].
What can be seen as a combination of the methods already presented (i.e., vertex enumeration and branch-and-bound) is the so-called sequential linear com-plementarity problem for solving linear and linear-quadratic bilevel programs, introduced in [118, 119]. This approach seems quite e cient for the solution of medium-scale problems.
Several descent methods have been proposed in literature for solving bilevel programming problems. A descent direction in bilevel optimization is a direction d P Rn along which the upper-level function value decreases while keeping bilevel feasibility. Given that a point is considered bilevel feasible only if it is lower-level optimal, nding a descent direction can be challenging. Indeed, a major issue is the availability of the gradient (or a sub-gradient) of the upper-level objective function at a feasible point. To tackle this problem, researchers have investigated ways to approximate the gradient of the upper-level objective [128] as well as considered formulation of auxiliary programs, like in [177] where the computation of the steepest descent direction for a bilevel problem without upper-level constraints is done with the help of a linear-quadratic bilevel problem. The sequential linear complementarity problem algorithm proposed in [119] is used to solve such linear-quadratic bilevel problem . The same approach of [177] is applied to convex bilevel programs, where the upper level is quadratic and the lower level is strictly convex quadratic programs, in [194].
Part of the literature is about penalty methods, which consist in solving a series of unconstrained problems, obtained by adding a term, called a penalty function, to the objective function measuring the violation of the constraints while relaxing them. The measure of violation is nonzero when the constraints are violated and is zero when constraints are not violated. Despite the large number of works focused on such methods, they are generally limited to computing stationary points and local minima. While in [14, 179, 15] only the lower level is penalized, and bilevel hierarchy is maintained, in [114] both upper and lower-level objective functions are penalized. In [202], a BLP is converted into a penalized bilinear optimization problem, and an exact penalty algorithm is proposed to nd the BLP optimal solution by solving a series of bilinear problems. In a number of works [39, 40, 56], the lower-level problem is replaced by its KKT conditions and, then, a penalized approach is used to solve the single-level problem. Recently, in [140], the authors use the KKT approach and, then, append the complementarity condition to the upper-level objective function with a penalty. The penalized problem is handled using a series of linear programs.
Some papers propose trust-region algorithms to solve bilevel programs. In trust-region methods a certain region of the objective function is approximated using a model function. Such region is expanded if the approximation is adequate, otherwise it is contracted. The rst trust-region technique to solve bilevel problems was presented in [136], when the lower-level problem has a strongly convex objective function and linear constraints, and no upper-level constraints are considered. Later, in [143] a bilevel problem is solved with a trust-region approach where the model is itself a bilevel problem with linear upper level and a linear variational inequality at the lower level. Similarly, in [64], the authors consider a bilevel program with no coupling constraints, and the model solved is a linear-quadratic bilevel problem, then reformulated using the KKT approach.
In many real systems, the leader or the follower may have to make discrete decisions. This type of decisions can be described by considering formulations where some variables are restricted to be integer [151]. Branch-and-bound algorithms for solving Bilevel Mixed-Integer Linear Problems (MIBLPs), and mixed-integer quadratic bilevel problems with di erent assumptions are proposed in [30, 201, 92] and [87], respectively.
To enhance the performance of their basic branch-and-bound method, the authors of [92] also introduce intersection cuts to cut o bilevel infeasible points, thus obtaining a branch-and-cut approach for MIBLPs. Another branch-and-cut algorithm is proposed in [81], for MIBLPs with only integer variables in both levels and no coupling constraints. An extension of the former method that allows for a mixed-integer setting at both levels is given by [185].
A cutting plane method using the Chvatal-Gomory cut for solving a bilevel program with continuous upper level and discrete lower level was proposed in [71]; the algorithm approximates the feasible set of the lower level.
In [107], two deterministic global optimization methods that solve mixed-integer nonlinear bilevel problems are proposed. The rst addresses problems in which the upper level is mixed-integer nonlinear and the lower level continuous nonlinear. The second solves problems in which the upper level involves mixed-integer nonlinear functions, and the lower level is mixed-integer nonlinear in upper-level variables, linear polynomial in lower integer variables, and linear in lower continuous variables. This second approach is based on the reformulation of the lower problem as continuous via its convex hull and solving the resulting nonlinear bilevel problem by a novel deterministic global optimization framework.
For the solution of bilevel problems with mixed-integer variables, also Benders decomposition techniques have been employed. Decomposition techniques exploit the decomposable structure of the problems in order to facilitate their solution through the resolution of a series of smaller sub-problems. In [173], the sub-problem is the slave problem which is obtained by xing a number of integer variables of the initial MIBLP to a feasible value. The master problem, instead, gives the optimal solution after the addition of Benders cuts. Fixing the integer values makes the slave problem a BLP, which is solved by KKT reformulation techniques, and its solution is used to add a Benders cut to the master problem. The algorithm iterates between master and slave problems until optimality criteria are met. In [45], a Benders-like decomposition is viewed as a procedure for iterative re nement of dual functions associated with the value function of a MIBLP involving integer variables also at the lower level.
In [211], a single-level reformulation and a decomposition algorithm based on a column-and-constraint generation scheme are proposed for MIBLPs with continuous and integer variables in both upper and lower-level programs. In [210], upper-level constraints involving lower-level variables are also considered, and the approach proposed in [211] is enhanced projecting the constraint region on the space of lower-level integer variables and working with KKT conditions of the remaining continuous lower-level problem.
Authors of [89] proposed a global solution approach using a parametric pro-gramming theory to address BLPs, Bilevel Quadratic Problems (BQPs) and MIBLPs with binary variables. Indeed, the follower’s problem can be solved as a multi-parametric programming problem, with parameters being the upper-level variables. By inserting the resulting exact parametric solutions into the upper level, the overall problem is transformed into a set of independent single-level problems, which can be solved to global optimality. The approach is extended to mixed-integer convex quadratic bilevel programs in [23]. The same authors provide a computational study for MIBLPs and mixed-integer BQPs in [170], where B-POP is presented, a MATLAB toolbox for bilevel optimization through multi-parametric programming. Very recently, in [48] another parametric approach is proposed for linearly constrained bilevel problems in which the upper-level objective function depends on both the lower-level primal and dual optimal solu-tions. When the upper-level objective is a ne in the lower-level primal optimal solution, the parametric function is piece-wise linear. This property facilitates the application of parametric programming and allows for decomposition of a separable lower-level problem. When the upper-level objective is bilinear in the lower-level primal and dual optimal solutions, the authors also provide an exact linearization method that reduces the bilevel problem to a single-level MILP problem. Obviously, the entire eld of bilevel optimization solution methods is broader and we, thus, are not able to cover it entirely in this dissertation. The readers may refer to [79] which contains the largest up-to-date list of references in the eld.
Conclusion
In this rst chapter we introduced the eld of bilevel programming, which is a useful tool to model real-world problems involving a hierarchical relationship between two decision levels. Indeed bilevel programming has been applied to: military problems, tra c and transportation applications (see, e.g., Chapter 4), management science, production planning, security, as well as energy networks and market (see Chapter 5). We presented the main approaches in this area that deal with theoretical issues, reformulations and algorithms. To close the discussion, in Chapter 2 we discuss the computational complexity of bilevel problems.
Table of contents :
Introduction
I Bilevel optimization
1 Bilevel programming
1.1 Introduction
1.2 Single-level reformulations
1.3 Solution approaches
1.4 Conclusion
2 Computational foundations of bilevel programming
2.1 Polynomial hierarchy and formulations with two classiers
2.2 Complexity of BLPs and MIBLPs
2.3 Polynomially solvable special cases
2.4 Independent bilevel problems
2.5 Conclusion
3 Solving a class of bilevel programs with quadratic lower level
3.1 Introduction
3.2 Literature review
3.3 Single-level formulation via the dual approach
3.3.1 SDP relaxation/reformulation of the lower-level problem
3.3.2 Dual SDP problem
3.3.3 SDP restriction/reformulation of the bilevel problem
3.4 Cutting plane algorithm
3.4.1 Convergence proof
3.4.2 A convergence rate for the CP algorithm
3.5 Applications
3.5.1 Constrained quadratic regression
3.5.2 Zero-sum game with cubic payo
3.6 Numerical results
3.7 Conclusion
II Applications
4 Aircraft conict resolution
4.1 Introduction
4.2 Literature review
4.3 Conict resolution via speed regulation
4.3.1 Natural formulation
4.3.2 Polynomial programming formulation
4.3.3 Bilevel formulation
4.3.4 KKT reformulation
4.3.5 Dual reformulations
4.4 Conict resolution via heading angle changes
4.4.1 Bilevel formulation
4.4.2 KKT reformulation
4.4.3 Dual reformulations
4.5 Cutting plane algorithm
4.6 Computational experiments
4.7 Conict resolution problem: a benchmark generator
4.8 Conclusion
5 ACOPF in a bilevel framework and the network design ACOPF
5.1 Introduction
5.2 Literature review
5.3 The bilevel formulation
5.3.1 Convex relaxation of the lower level
5.3.2 Bilevel formulation with a convex lower-level problem
5.4 The network design ACOPF
5.4.1 ACOPF relaxations
5.4.2 ACOPFLrelaxations
5.4.3 Computational experiments
5.5 Conclusion
Conclusion
Appendices
