• 论文 • 上一篇    下一篇

一类非负二次整数规划问题的分支定界缩减方法

高岳林, 魏飞   

  1. 北方民族大学信息与系统科学研究所, 银川 750021
  • 收稿日期:2010-02-08 出版日期:2011-08-15 发布日期:2011-09-03
  • 基金资助:

    国家自然科学基金项目资助(60962006),宁夏自然科学基金项目资助(NZ0848).

高岳林, 魏飞. 一类非负二次整数规划问题的分支定界缩减方法[J]. 计算数学, 2011, 33(3): 233-248.

Gao Yuelin, Wei Fei. A BRANCH-AND-BOUND REDUCED METHOD FOR A CLASS OF NON-NEGATIVE INTEGER QUADRATIC PROGRAMMING PROBLEMS[J]. Mathematica Numerica Sinica, 2011, 33(3): 233-248.

A BRANCH-AND-BOUND REDUCED METHOD FOR A CLASS OF NON-NEGATIVE INTEGER QUADRATIC PROGRAMMING PROBLEMS

Gao Yuelin, Wei Fei   

  1. Beifang University for Nationalities, Institute of Information and System Sciences, Yinchuan 750021, China
  • Received:2010-02-08 Online:2011-08-15 Published:2011-09-03
针对一类非负整数二次规划问题, 提出了一个新的分枝定界缩减方法.在这个方法里, 使用了一个新的超矩形二分技术和一个新的线性规划松弛定下界技术, 同时为了提高逼近程度和加快收敛速度, 使用了超矩形缩减策略. 数值结果表明所提出的算法是可行的和有效的.
For a class of non-negative integer quadratic programming problems, a new branch-and-bound reduced method is proposed. In this method, a new rectangular two-partitioned technique and a new linear programming relaxation bounded technique are used. At the same time, in order to improve the degree of approximation and the convergence rate of acceleration, a rectangular reduction strategy is used. Numerical results show that the proposed algorithm is feasible and effective and can solve the middle-larger scale problems.

MR(2010)主题分类: 

()
[1] Fletcher R, Leyffer S. Solving mixed intger nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66: 327-349.

[2] Mathur K, Salkin H M, Morito S. A branch and search algorithm for a class of nonlinear knapsack problems[J]. Operations Research Letters, 1983, 2: 155-160.

[3] 黄红选, 梁治安. 全局优化引论[M]. 北京: 清华大出版社, 2003.

[4] Al-Khayyal, F A, Falk, J E. Jointly constrained biconvex programming[J]. Math. Oper. Res., 1983, 8: 273-286.

[5] Juan M. Zamora and Ignacio E. Grossmann: A Branch and Contract Algorithm for Problems with Concave Univariate, Bilinear and Linear Fractional Terms[J]. Journal of Global Optimization, 1999, 14: 217-249.

[6] Ryoo H S, Sahindis N V. Global Optimization of Multiplicative Programs[J]. Journal of Global Optimization, 2003, 26: 387-418.

[7] Kuno T, communicated by Benson H P. Solving a Class of Multiplicative Programs with 0-1 Knapsack Constraints1[J]. Journal of Optimization Theory and Applications, 1999, 103: 121-135.

[8] Stubbs R, Mehrotea S. Abranch-and-cut method for 0-1 mixed convex programming[J]. Mathematical Programming, 1999, 86: 512-532.

[9] 陈志平, #

[48] 峰. 求解中大规模复杂凸二次整数规划问题的新型分枝定界算法[J]. 计算数学, 2004, 26(4).

[10] 陈志平, 李乃成, #

[48] 峰. 解复杂二次整数规划问题的新型分枝定界算法[J]. 工 程数学学报, 2004, 21(3).

[11] 陈志平, 徐宗本. 计算机数学[M]. 北京: 科学出版社, 2001.

[12] Anjidani M, Effati S. Steepest descent method for solving zero-one nonlinear programming problems[J]. Applied Mathematics and Computation, 2007, 193: 197-202.

[13] Westerlund T, Petterssonv F. A cutting plane method for solving convex MINLP proplems[J]. Comuter and Chemical Engineering, 1995, 19: 131-136.

[14] Ivo Nowak, Stefan Vigerske. LaGO: a (heuristic) Branch and Cut algorithm for nonconvex MINL-Ps[J]. CEJOR, 2008, 16: 127-138.

[15] Bergamini M L, Grossmann I, Scenna N, Aguirre P. An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms[J]. Computers and Chemical Engineering, 2008, 32: 477-493.

[16] Gao Yuelin, Wang Yanjun and Du Xuewu. A two-level relaxed bound method for a nonlinear class of 0-1 knapsack problems[J]. Intelligent Information Management Systems and Technologies, 2005, 3: 461-470.

[17] Flippo O E, Rinnoy Kan A H G. A note on Benders decomposion in mixed-integer quadratic programming[J]. Operations Research Letters, 1990, 9: 81-83.
[1] 高岳林, 张博. 线性比式和规划问题的输出空间分支定界算法[J]. 计算数学, 2020, 42(2): 207-222.
[2] 高岳林, 井霞. 一类线性乘积规划问题的分支定界缩减方法[J]. 计算数学, 2013, 35(1): 89-98.
阅读次数
全文


摘要