共查询到20条相似文献,搜索用时 31 毫秒
1.
以下层问题的K-T最优性条件代替下层问题,将线性二层规划转化为相应的单层规划问题,通过分析单层规划可行解集合的结构特征,设计了一种求解线性二层规划全局最优解的割平面算法.数值结果表明所设计的割平面算法是可行、有效的. 相似文献
2.
本文针对线性双层规划问题提出一个由KMY算法演变而来的原对偶内点算法.与现在很多线性双层规划单纯型算法不同,作者提出的算法从一可行初始点穿过约束多面体内部直接得到近似最优解,当约束条件和变量数目增加时,本算法的迭代次数和计算时间变化很小.所以大大提高实际可操作性能和运算效率. 相似文献
3.
A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience 总被引:7,自引:0,他引:7
We consider the approximation of nonlinear bilevel mathematical programs by solvable programs of the same type, i.e., bilevel programs involving linear approximations of the upper-level objective and all constraint-defining functions, as well as a quadratic approximation of the lower-level objective. We describe the main features of the algorithm and the resulting software. Numerical experiments tend to confirm the promising behavior of the method. 相似文献
4.
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. 相似文献
5.
6.
7.
基于双层线性分式规划的性质,讨论了上层不带约束的双层线性分式规划模型,给出了求其所有顶点的算法.此算法为进一步进行双层线性分式规划的灵敏度分析打下了坚实的基础,通过例子对算法进行了检验,并利用结果进行了灵敏度分析. 相似文献
8.
9.
多表旋转算法是一种基于旋转算法来求解线性二层规划问题的方法,通过表格组合还可以求解线性多层规划、以及线性一主多从有关联的stackelberg-nash均衡等问题,求解的思想是使用旋转算法,在多个主体间通过约束传递达到均衡。通过算例显示该方法可以迅速地算出局部最优解,如果问题的诱导域是连通的,还可以计算出全局最优解。 相似文献
10.
Audet C. Hansen P. Jaumard B. Savard G. 《Journal of Optimization Theory and Applications》1997,93(2):273-300
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. 相似文献
11.
12.
In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada). 相似文献
13.
M. Ehrgott J. Puerto A. M. Rodríguez-Chía 《Journal of Optimization Theory and Applications》2007,134(3):483-497
We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem
of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate
the algorithm by an example, present some numerical results, give some further details on special cases and point out future
research.
The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian
Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275.
The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909
and HA2003-0121.
We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose
comments have helped us to improve the presentation of the paper. 相似文献
14.
15.
16.
We are interested in a class of linear bilevel programs where the upper level is a linear scalar optimization problem and the lower level is a linear multi-objective optimization problem. We approach this problem via an exact penalty method. Then, we propose an algorithm illustrated by numerical examples. 相似文献
17.
The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set EP nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported. 相似文献
18.
通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程. 相似文献
19.
20.
Le Thi Hoai An Pham Dinh Tao Nam Nguyen Canh Nguyen Van Thoai 《Journal of Global Optimization》2009,44(3):313-337
We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function
in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming
problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known
in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported. 相似文献