Designing robust coverage networks to hedge against worst-case facility losses

In order to design a coverage-type service network that is robust to the worst instances of long-term facility loss, we develop a facility location–interdiction model that maximizes a combination of initial coverage by p facilities and the minimum coverage level following the loss of the most critical r facilities. The problem is formulated both as a mixed-integer program and as a bilevel mixed-integer program. To solve the bilevel program optimally, a decomposition algorithm is presented, whereby the original bilevel program is decoupled into an upper level master problem and a lower level subproblem. After sequentially solving these problems, supervalid inequalities can be generated and appended to the upper level master in an attempt to force it away from clearly dominated solutions. Computational results show that when solved to optimality, the bilevel decomposition algorithm is up to several orders of magnitude faster than performing branch and bound on the mixed-integer program.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Bilevel optimization: on the structure of the feasible set

We consider bilevel optimization from the optimistic point of view. Let the pair (x, y) denote the variables. The main difficulty in studying such problems lies in the fact that the lower level contains a global constraint. In fact, a point (x, y) is feasible if y solves a parametric optimization problem L(x). In this paper we restrict ourselves to the special case that the variable x is one-dimensional. We describe the generic structure of the feasible set M. Moreover, we discuss local reductions of the bilevel problem as well as corresponding optimality criteria. Finally, we point out typical problems that appear when trying to extend the ideas to higher dimensional x-dimensions. This will clarify the high intrinsic complexity of the general generic structure of the feasible set M and corresponding optimality conditions for the bilevel problem U.     

A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

Strong-Weak Nonlinear Bilevel Problems: Existence of Solutions in a Sequential Setting

The paper deals with a strong-weak nonlinear bilevel problem which generalizes the well-known weak and strong ones. In general, the study of the existence of solutions to such a problem is a difficult task. So that, for a strong-weak nonlinear bilevel problem, we first give a regularization based on the use of strict ??-solutions of the lower level problem. Then, via this regularization and under sufficient conditions, we show that the problem admits at least one solution. The obtained result is an extension and an improvement of some recent results appeared recently in the literature for both weak nonlinear bilevel programming problems and linear finite dimensional case.     

On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem

This paper is mainly concerned with the classical KKT reformulation and the primal KKT reformulation (also known as an optimization problem with generalized equation constraint (OPEC)) of the optimistic bilevel optimization problem. A generalization of the MFCQ to an optimization problem with operator constraint is applied to each of these reformulations, hence leading to new constraint qualifications (CQs) for the bilevel optimization problem. M- and S-type stationarity conditions tailored for the problem are derived as well. Considering the close link between the aforementioned reformulations, similarities and relationships between the corresponding CQs and optimality conditions are highlighted. In this paper, a concept of partial calmness known for the optimal value reformulation is also introduced for the primal KKT reformulation and used to recover the M-stationarity conditions.     

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.     

On Bilevel Programs with a Convex Lower-Level Problem Violating Slater’s Constraint Qualification

This paper focuses on bilevel programs with a convex lower-level problem violating Slater’s constraint qualification. We relax the constrained domain of the lower-level problem. Then, an approximate solution of the original bilevel program can be obtained by solving this perturbed bilevel program. As the lower-level problem of the perturbed bilevel program satisfies Slater’s constraint qualification, it can be reformulated as a mathematical program with complementarity constraints which can be solved by standard algorithms. The lower convergence properties of the constraint set mapping and the solution set mapping of the lower-level problem of the perturbed bilevel program are expanded. We show that the solutions of a sequence of the perturbed bilevel programs are convergent to that of the original bilevel program under some appropriate conditions. And this convergence result is applied to simple trilevel programs.     

二(双)层规划综述

二(双)层规划是研究二层决策的递阶优化问题.其理论、方法和应用在过去的30多年取得了很大的发展.本文对二层规划问题的基本概念、性质和算法作了综述,并且对下层规划问题的解不唯一的情况也作了介绍,最后还给出了几种常见的二层规划模型.     

下层独立的一主多从双层随机线性规划问题研究

Herminia I.Calvete等研究了一主多从双层确定性线性规划问题,证明了这类问题等价于一类常规的双层线性规划问题.本文在此基础上,推广确定型的问题到随机型优化情况,考虑了一类下层优化相互独立的一主多从双层随机优化问题(SLBMFP).在特定的随机变量分布条件下,理论上证明了该类问题可以转化为一主一从双层确定性优化问题.本文的研究对于求解一主多从双层随机优化模型,解决此类模型在实际应用中的问题具有一定的意义.     

Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

Necessary optimality conditions for a special class of bilevel programming problems with unique lower level solution

We consider a bilevel programming problem in Banach spaces whose lower level solution is unique for any choice of the upper level variable. A condition is presented which ensures that the lower level solution mapping is directionally differentiable, and a formula is constructed which can be used to compute this directional derivative. Afterwards, we apply these results in order to obtain first-order necessary optimality conditions for the bilevel programming problem. It is shown that these optimality conditions imply that a certain mathematical program with complementarity constraints in Banach spaces has the optimal solution zero. We state the weak and strong stationarity conditions of this problem as well as corresponding constraint qualifications in order to derive applicable necessary optimality conditions for the original bilevel programming problem. Finally, we use the theory to state new necessary optimality conditions for certain classes of semidefinite bilevel programming problems and present an example in terms of bilevel optimal control.     

A new equivalent single-level problem for bilevel problems

In this article, we give necessary optimality conditions for a bilevel optimization problem (P). An intermediate single-level problem (Q), which is equivalent to the bilevel optimization problem (P), has been introduced.     

An extended branch and bound algorithm for linear bilevel programming

For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn–Tucker conditions. However, one principle challenge is that it could not well handle a linear bilevel programming problem when the constraint functions at the upper-level are of arbitrary linear form. This paper proposes an extended branch and bound algorithm to solve this problem. The results have demonstrated that the extended branch and bound algorithm can solve a wider class of linear bilevel problems can than current capabilities permit.     

Model and extended Kuhn–Tucker approach for bilevel multi-follower decision making in a referential-uncooperative situation

When multiple followers are involved in a bilevel decision problem, the leader’s decision will be affected, not only by the reactions of these followers, but also by the relationships among these followers. One of the popular situations within this bilevel multi-follower issue is where these followers are uncooperatively making their decisions while having cross reference to decision information of the other followers. This situation is called a referential-uncooperative situation in this paper. The well-known Kuhn–Tucker approach has been previously successfully applied to a one-leader-and-one-follower linear bilevel decision problem. This paper extends this approach to deal with the above-mentioned linear referential-uncooperative bilevel multi-follower decision problem. The paper first presents a decision model for this problem. It then proposes an extended Kuhn–Tucker approach to solve this problem. Finally, a numerical example illustrates the application of the extended Kuhn–Tucker approach.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

A neural network for solving a convex quadratic bilevel programming problem

A neural network is proposed for solving a convex quadratic bilevel programming problem. Based on Lyapunov and LaSalle theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed network does converge to the equilibrium, which corresponds to the optimal solution of a convex quadratic bilevel programming problem. Numerical simulation results show that the proposed neural network is feasible and efficient for a convex quadratic bilevel programming problem.