线性双层规划的改进PCP全局求解算法

doi:10.12005/orms.2021.0004

运筹与管理 ›› 2021, Vol. 30 ›› Issue (1): 23-28.DOI: 10.12005/orms.2021.0004

线性双层规划的改进PCP全局求解算法

杨静蕾¹, 罗梅丰², 袁帅石¹

1.南开大学商学院管理科学与工程系,中国天津 300071;
2.香港理工大学物流及航运系,中国香港

收稿日期:2018-04-12 出版日期:2021-01-25
通讯作者: 罗梅丰(1964-),香港人,副教授,博士,研究方向:交通网络优化等。
作者简介:杨静蕾(1974-)女,河北定州人,副教授,博士,研究方向:物流系统优化等。
基金资助:
国家自然科学基金资助项目(NSFC61772290)

An Extended Global PCPAlgorithm for Linear Bilevel Programming

YANG Jing-lei¹, LUO Mei-feng², YUAN Shuai-shi¹

1. Department of Management science and Engineering, Business School, Nankai University, Tianjin 300071, China;
2. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong, China

Received:2018-04-12 Online:2021-01-25

摘要/Abstract

摘要： 本文采用K-T条件将线性双层规划模型改写为单层规划后,将参数引入上层目标函数,构造了含参线性互补问题(PLCP)并给出它的一些性质。进而通过改进Lemke算法的进基规则,在保持互补旋转算法原有优势的基础上,引入充分小正数ε,设计了改进参数互补旋转(PCP)算法求取全局最优解,最后通过两个算例说明了其有效性。

关键词: 线性双层规划, PCP算法, 互补旋转, 线性互补问题

Abstract: After reformulating the linear bilevel programming model into a single level problem with the K-T conditions, we introduce a parameter into the upper level objective function to construct the Parametric Linear Complementary Problem (PLCP), whose properties are discussed in this paper. Then an extended Parametric Complementary Pivot (PCP) algorithm is proposed based on some modifications of the rules for determining the entering basis variable in Lemke's Algorithm after introducing a sufficiently small positive numberε. The extended PCP algorithm, which maintains the original advantages of the complementary pivoting approach, can achieve the global optimal solution. The computational results of two examples demonstrate that this algorithm is effective.

Key words: linear bilevel programming, PCP algorithm, complementary pivot, linear complementary problem

中图分类号:

O221.1

杨静蕾, 罗梅丰, 袁帅石. 线性双层规划的改进PCP全局求解算法[J]. 运筹与管理, 2021, 30(1): 23-28.

YANG Jing-lei, LUO Mei-feng, YUAN Shuai-shi. An Extended Global PCPAlgorithm for Linear Bilevel Programming[J]. Operations Research and Management Science, 2021, 30(1): 23-28.

参考文献

[1] Sinha A, Malo P, Deb K. A review on bilevel optimization: from classical to evolutionary approaches and applications[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(2): 276-295.
[2] Dempe S, Kalashnikov V, Prez-Valds G A, et al. Bilevel programming problems: theory, algorithms and applications to energy networks[M]. Springer Publishing Company, Incorporated, 2015.
[3] Colson B, Marcotte P, Savard G. Bilevel programming: a survey[J]. 4OR, 2005, 3(2): 87-107.
[4] Bialas W, Karwan M. On two-level optimization[J]. IEEE Transactions on Automatic Control, 1982, 27(1): 211-214.
[5] Candler W, Townsley R. A linear two-level programming problem[J]. Computers & Operations Research, 1982, 9(1): 59-76.
[6] White D, Anandalingam G, A penalty function approach for solving bi-level linear programs[J]. Journal of Global Optimization, 1993, (3): 397-419.
[7] Campêlo M, Scheimberg S. A simplex approach for finding local solutions of a linear bilevel program by equilibrium points[J]. Annals of Operations Research, 2005, 138(1): 143-157.
[8] Lv Y, Hu T, Wang G, et al. A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming[J]. Applied Mathematics & Computation, 2007, 188(1): 808-813.
[9] 王广民,万仲平,王先甲.二(双)层规划综述[J].数学进展,2007,36(5):513-529.
[10] Audet C, Savard G, Zghal W. New branch-and-cut algorithm for bilevel linear programming[J]. Journal of Optimization Theory & Applications, 2007, 134(2): 353-370.
[11] Hansen P, Jaumard B, Savard G. New branch-and-bound rules for linear bilevel programming[J]. SIAM Journal on Scientific and Statistical Computing, 1992, (13): 1194-1217.
[12] Shi C, Lu J, Zhang G, et al. An extended branch and bound algorithm for linear bilevel programming[J]. Applied Mathematics & Computation, 2006, 180(2): 529-537.
[13] 黄正海,林贵华,修乃华.变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J].运筹学学报,2014,18(1):113-133.
[14] Cottle R W, Dantzig G B. Complementary pivot theory of mathematical programming[J]. Linear Algebra & Its Applications, 1968, 1(1): 103-125.
[15] Lemke C E. Bimatrix equilibrium points and mathematical programming[J]. Management Science, 1965, 11(7): 681-689.
[16] Bialas W F, Karwan M H, Shaw J. A parametric complementary pivot approach to multilevel programming[M]. Research Report No. 80-2. Department of Industrial Engineering SUNY at Buffalo, 1980.
[17] Bialas W F, Karwan M H. Two-level linear programming[J]. Management Science, 1984, 30(8): 1004-1020.
[18] Ben-Ayed O, Blair C E. Computational difficulties of bilevel linear programming[J]. Operations Research, 1990, 38(3): 556-560.
[19] Júdice J J, Faustino A M. A sequential LCP method for bilevel linear programming[J]. Annals of Operations Research, 1992, 34(1): 89-106.
[20] 赵茂先,李桂玲.一个求解线性双层规划的全局收敛算法[J].山东科技大学学报(自然科学版),2007,26(5):75-79.
[21] Shi C, Lu J, Zhang G. An extended Kuhn-Tucker approach for linear bilevel programming[J]. Applied Mathematics & Computation, 2005, 162(1): 51-63.
[22] Júdice J J, Sherali H D, Ribeiro I M, et al. Complementarity active-set algorithm for mathematical programming problems with equilibrium constraints[J]. Journal of Optimization Theory & Applications, 2007, 134(3): 467-481.

线性双层规划的改进PCP全局求解算法

An Extended Global PCPAlgorithm for Linear Bilevel Programming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	张志鹏,迟国泰. 基于随机久期利率免疫的银行资产负债优化模型[J]. 运筹与管理, 2018, 27(8): 135-148.
[2]	张京亮, 陈之宁. 含直觉模糊弹性约束的广义模糊变量线性规划[J]. 运筹与管理, 2016, 25(6): 105-111.
[3]	秦长城. 一种改进的投资组合模型的算法和实证分析[J]. 运筹与管理, 2016, 25(2): 226-232.
[4]	周学松, 赵恒. 线性规划中一个避免人工变元的方法的改进[J]. 运筹与管理, 2011, 20(5): 31-38.