A Bridge Between Bilevel Programs and Nash Games

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our “uneven” horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our “uneven” horizontal model, in some sense, lies between the vertical bilevel model and a “pure” horizontal game.     

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.     

Exact Penalty Functions for Convex Bilevel Programming Problems

In this paper, we propose a new constraint qualification for convex bilevel programming problems. Under this constraint qualification, a locally and globally exact penalty function of order 1 for a single-level reformulation of convex bilevel programming problems is given without requiring the linear independence condition and the strict complementarity condition to hold in the lower-level problem. Based on these results, locally and globally exact penalty functions for two other single-level reformulations of convex bilevel programming problems can be obtained. Furthermore, sufficient conditions for partial calmness to hold in some single-level reformulations of convex bilevel programming problems can be given.     

Reducibility of bilevel programming problems to vector optimization problems

Reductions are studied of the bilevel programming problems to vector (multicriteria) optimization problems. A general framework is proposed for constructing these reductions. Some particular cases of bilevel problems are considered.     

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 mathematical model of market competition

We consider a mathematical model of decision making by a company attempting to win a market share. We assume that the company releases its products to the market under the competitive conditions that another company is making similar products. Both companies can vary the kinds of their products on the market as well as the prices in accordance with consumer preferences. Each company aims to maximize its profit. A mathematical statement of the decision-making problem for the market players is a bilevel mathematical programming problem that reduces to a competitive facility location problem. As regards the latter, we propose a method for finding an upper bound for the optimal value of the objective function and an algorithm for constructing an approximate solution. The algorithm amounts to local ascent search in a neighborhood of a particular form, which starts with an initial approximate solution obtained simultaneously with an upper bound. We give a computational example of the problem under study which demonstrates the output of the algorithm.     

求解二层规划问题的遗传算法

本文求解二层规划问题的遗传算法，给出了算法基本框架并对算法实现进行了研究．算法适用于各类线性和非线性二层规划问题．数值计算结果显示，该方法是可行和有效的．     

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.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.     

OD估计双层规划扩展模型

利用双层规划模型进行OD估计,建立双层规划扩展模型.考虑OD估计问题中的随机误差,基于Bayes估计和多元正态分布建立上层目标函数;考虑用户路径选择行为的随机性,基于随机用户均衡建立需求可变动的下层目标函数,同时该扩展模型能适应我国混合交通的实际,既能适用于拥挤网络、也能适用于非拥挤网络,最后通过算例证明此模型的有效性.     

一种非增值型凸二次双层规划的有效算法

主要研究了非增值型凸二次双层规划的一种有效求解算法。首先利用数学规划的对偶理论,将所求双层规划转化为一个下层只有一个无约束凸二次子规划的双层规划问题.然后根据两个双层规划的最优解和最优目标值之间的关系,提出一种简单有效的算法来解决非增值型凸二次双层规划问题.并通过数值算例的计算结果说明了该算法的可行性和有效性。     

基于动态定价的再制造商主导的多周期多目标产品回收网络设计

假设回收商和制造/再制造商为独立理性的决策者,并共同构建回收网络,且制造/再制造商在两者的博弈中处于主导地位。另考虑废旧品回收率是回收价格的线性函数,结合回收定价与回收网络设计,建立基于动态定价的回收网络双层规划模型,上层规划为制造/再制造商进行再制造工厂的选址,确定回收补贴价格,下层规划为回收商进行回收中心的选址,确定废旧品的回收价格。通过建立模型求解算法,并给出算例论证模型的有效性。     

An Objective Penalty Function of Bilevel Programming

Penalty methods are very efficient in finding an optimal solution to constrained optimization problems. In this paper, we present an objective penalty function with two penalty parameters for inequality constrained bilevel programming under the convexity assumption to the lower level problem. Under some conditions, an optimal solution to a bilevel programming defined by the objective penalty function is proved to be an optimal solution to the original bilevel programming. Moreover, based on the objective penalty function, an algorithm is developed to obtain an optimal solution to the original bilevel programming, with its convergence proved under some conditions.     

关于二层规划的逼近问题

下层问题以上层决策变量作为参数,而上层是以下层问题的最优值作为响应 的一类最优化问题——二层规划问题。我们给出了由一系列此类二层规划去逼近原二层规划的逼近法,得到了这种逼近的一些有趣的结果.     

风险厌恶条件下竞争报童问题的二层规划模型

有效应用数学规划方法研究报童类产品的库存管理,能够降低企业的成本和风险,从而提高企业的经济效益.此类问题的研究,目前主要集中在应用Nash博弈研究竞争报童问题以及零售商所持风险态度对供应链库存水平的影响.试图研究序贯决策下的竞争报童问题模型以及零售商所持风险态度对供应链库存水平的影响.由此建立了二层规划模型.算例表明序贯决策的竞争报童问题中,总订购量随风险厌恶程度的提高而降低.     

求解线性二层规划问题的多表旋转算法

多表旋转算法是一种基于旋转算法来求解线性二层规划问题的方法,通过表格组合还可以求解线性多层规划、以及线性一主多从有关联的stackelberg-nash均衡等问题,求解的思想是使用旋转算法,在多个主体间通过约束传递达到均衡。通过算例显示该方法可以迅速地算出局部最优解,如果问题的诱导域是连通的,还可以计算出全局最优解。     

A new descent algorithm for solving quadratic bilevel programming problems

1. IntroductionA bilevel programming problem (BLPP) involves two sequential optimization problems where the constraint region of the upper one is implicitly determined by the solutionof the lower. It is proved in [1] that even to find an approximate solution of a linearBLPP is strongly NP-hard. A number of algorithms have been proposed to solve BLPPs.Among them, the descent algorithms constitute an important class of algorithms for nonlinear BLPPs. However, it is assumed for almost all…