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

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

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.     

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

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

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.     

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.     

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

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

The <Emphasis Type="Italic">K</Emphasis>th-Best Approach for Linear Bilevel Multi-follower Programming

The majority of research on bilevel programming has centered on the linear version of the problem in which only one leader and one follower are involved. This paper addresses linear bilevel multi-follower programming (BLMFP) problems in which there is no sharing information among followers. It explores the theoretical properties of linear BLMFP, extends the Kth-best approach for solving linear BLMFP problems and gives a computational test for this approach.     

THE CONVERGENCE OF APPROACH PENALTY FUNCTION METHOD FOR APPROXIMATE BILEVEL PROGRAMMING PROBLEM

' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com…     

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.     

双层线性分式规划求顶点的算法

基于双层线性分式规划的性质,讨论了上层不带约束的双层线性分式规划模型,给出了求其所有顶点的算法.此算法为进一步进行双层线性分式规划的灵敏度分析打下了坚实的基础,通过例子对算法进行了检验,并利用结果进行了灵敏度分析.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

关于线性二层规划分枝定界方法的探讨

对求解线性二层规划的分枝定界方法进行了探讨.给出的一个例子表明,目前的分枝定界方法不能很好地解决上层带有任意线性形式约束的线性二层规划问题,进而在线性二层规划新定义的基础上提出了求解线性二层规划的扩展分枝定界方法.算例表明扩展分枝定界方法可以有效解决原分枝定界方法的不足.     

Test problem construction for linear bilevel programming problems

A method of constructing test problems for linear bilevel programming problems is presented. The method selects a vertex of the feasible region, far away from the solution of the relaxed linear programming problem, as the global solution of the bilevel problem. A predetermined number of constraints are systematically selected to be assigned to the lower problem. The proposed method requires only local vertex search and solutions to linear programs.     

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.     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.     

求解不确定型二层线性规划模型的悲观决策方法

基于多参数线性规划理论，将不确定型二层线性规划问题转化为多个关于不确定参数的线性规划问题。利用不确定型决策方法中的悲观准则．从最不利的结果中选择最有利的结果，从而得到不确定型二层线性规划的最优解。数值实例的仿真结果表明，所提出的悲观决策方法对解决诸如不确定供应链的规划与运作等问题不失为一种有效的决策支持工具。     

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

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

Solving linear fractional bilevel programs

In this paper, we prove that an optimal solution to the linear fractional bilevel programming problem occurs at a boundary feasible extreme point. Hence, the Kth-best algorithm can be proposed to solve the problem. This property also applies to quasiconcave bilevel problems provided that the first level objective function is explicitly quasimonotonic.