线性乘积和规划问题的基于D.C.松弛的分支定界算法

doi:10.15960/j.cnki.issn.1007-6093.2025.04.013

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (4): 159-174.doi: 10.15960/j.cnki.issn.1007-6093.2025.04.013

线性乘积和规划问题的基于D.C.松弛的分支定界算法

张博¹, 王红雨², 高岳林^1,†

1. 北方民族大学数学与信息科学学院, 宁夏银川 750021;
2. 宁夏大学土木与水利工程学院, 宁夏银川 750021

收稿日期:2022-09-10 出版日期:2025-12-15 发布日期:2025-12-11
通讯作者: 高岳林 E-mail:gaoyuelin8@163.com
基金资助:
国家自然科学基金(Nos.12301401,12461053),宁夏自然科学基金(No.2025AAC030059),宁夏高等教育一流学科建设项目基金(No.NXYLXK2017B09),北方民族大学重大专项(No.ZDZX201901),南京证券支持基础学科研究项目(No.NJZQJCXK202201)

A D.C. relaxation based branch-and-bound algorithm for sum-of-linear-products programming problems

ZHANG Bo¹, WANG Hongyu², GAO Yuelin^1,†

1. School of Mathematics and Information Science, North Minzu University, Yinchuan 750021, Ningxia, China;
2. School of Civil and Hydraulic Engineering, Ningxia University, Yinchuan 750021, Ningxia, China

Received:2022-09-10 Online:2025-12-15 Published:2025-12-11

摘要/Abstract

摘要： 线性乘积和规划已出现在工程实践和管理科学等领域, 是一类NP-难问题。针对该问题目标函数的特殊结构, 将其重构为一个D.C. (difference of convex functions) 规划问题。再利用凹函数的凸包络, 构造出了一种D.C.松弛问题, 并将其分解为两个凸子问题。然后将该D.C. 松弛与超矩形的标准二分法相结合, 设计了新的分支定界算法, 并分析了其理论收敛性和计算复杂度。最后, 借助大量数值实验验证了该算法的有效性。

关键词: 全局优化, 线性乘积和规划, 分支定界, D.C.规划松弛技术

Abstract: The sum-of-linear-products program has appeared in fields such as engineering practice and management science, and it is a class of NP-Hard problems. In view of the special structure of the objective function of this problem, it is reconstructed as a D.C. (difference of convex functions) programming problem. Based on the convex envelope of concave function, a D.C. relaxation subproblem is constructed and decomposed into two convex optimization problems. Then, by combining the D.C. relaxation with the standard bisection method of hyperrectangle, a new branch and bound algorithm is designed, and its theoretical convergence and computational complexity are analyzed. Finally, the effectiveness of the algorithm is verified by a large number of numerical experiments.

Key words: global optimization, sum-of-linear-products programming problem, branch and bound, D.C. programming relaxation technique

中图分类号:

O221.2

张博, 王红雨, 高岳林. 线性乘积和规划问题的基于D.C.松弛的分支定界算法[J]. 运筹学学报（中英文）, 2025, 29(4): 159-174.

ZHANG Bo, WANG Hongyu, GAO Yuelin. A D.C. relaxation based branch-and-bound algorithm for sum-of-linear-products programming problems[J]. Operations Research Transactions, 2025, 29(4): 159-174.

参考文献

[1] Quesada I, Grossmann I E. Alternative bounding approximations for the global optimization of various engineering design problems [M]//Grossmann I E. (ed.) Global Optimization in Engineering Design, Nonconvex Optimization and Its Applications, Boston: Springer, 1996, 9: 309-331.
[2] Mulvey J M, Vanderbei R J, Zenios S A. Robust optimization of large-scale systems [J]. Operations Research, 1995, 43(2): 264-281.
[3] Alberto C, Laura M. Generalized Convexity and Optimization: Theory and Applications [M]. Berlin: Springer, 2009.
[4] Cambini R, Sodini C. On the minimization of a class of generalized linear functions on a flow polytope [J]. Optimization, 2014, 63(10): 1449-1464.
[5] Bennett K P. Global tree optimization: A non-greedy decision tree algorithm [J]. Computing Science and Statistics, 1994, 26(1): 156-156.
[6] Bennett K P, Mangasarian O L. Bilinear separation of two sets in n-space [J]. Computational Optimization and Applications, 1993, 2(3): 207-227.
[7] Matsui T. NP-hardness of linear multiplicative programming and related problems [J]. Journal of Global Optimization, 1996, 9(2): 113-119.
[8] Shen P, Huang B. Global algorithm for solving linear multiplicative programming problems [J]. Optimization Letters, 2020, 14(3): 693-710.
[9] Gao Y, Xu C, Yang Y. An outcome-space finite algorithm for solving linear multiplicative programming [J]. Applied Mathematics and Computation, 2006, 179(2): 494-505.
[10] Benson H P, Boger G M. Outcome-space cutting-plane algorithm for linear multiplicative programming [J]. Journal of Optimization Theory and Applications, 2000, 104(2): 301-322.
[11] Wang C F, Liu S Y, Shen P P. Global minimization of a generalized linear multiplicative programming [J]. Applied Mathematical Modelling, 2012, 36(6): 2446-2451.
[12] Shen P, Wang K, Lu T. Outer space branch and bound algorithm for solving linear multiplicative programming problems [J]. Journal of Global Optimization, 2020, 78(3): 453-482.
[13] Wang C F, Deng Y P, Shen P P. A novel convex relaxation-strategy-based algorithm for solving linear multiplicative problems [J]. Journal of Computational and Applied Mathematics, 2022, 407(1): 114080.
[14] Ryoo H S, Sahinidis N V. Global optimization of multiplicative programs [J]. Journal of Global Optimization, 2003, 26(4): 387-418.
[15] Wang C F, Bai Y Q, Shen P P. A practicable branch-and-bound algorithm for globally solving linear multiplicative programming [J]. Optimization, 2017, 66(3): 397-405.
[16] Horst R, Tuy H. Global Optimization: Deterministic Approaches [M]. Deutschland: Springer Science & Business Media, 2013.
[17] Youness E A. Level set algorithm for solving convex multiplicative programming problems [J]. Applied Mathematics and Computation, 2005, 167(2): 1412-1417.
[18] Liu S, Zhao Y. An efficient algorithm for globally solving generalized linear multiplicative programming [J]. Journal of Computational and Applied Mathematics, 2016, 296(1): 840-847.
[19] Falk J, Palocsay S. Image space analysis of generalized fractional programs [J]. Journal of Global Optimization, 1994, 4(1): 63-88.
[20] Konno H, Kuno T. Linear multiplicative programming [J]. Mathematical Programming, 1992, 56(1-3): 51-64.
[21] Oliveira R M, Ferreira P A V. An outcome space approach for generalized convex multiplicative programs [J]. Journal of Global Optimization, 2010, 47(1): 107-118.
[22] Charkhgard H, Savelsbergh M, Talebian M. A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints [J]. Computers and Operations Research, 2018, 89(1): 17-30.
[23] Thuy L Q, Kim N T B, Thien N T. Generating efficient outcome points for convex multiobjective programming problems and its application to convex multiplicative programming [J]. Journal of Applied Mathematics, 2011, 11(1): 1-21.
[24] Jiao H, Liu S, Chen Y. Global optimization algorithm for a generalized linear multiplicative programming [J]. Journal of Applied Mathematics and Computing, 2012, 40(1): 551-568.
[25] Shen P P, Wang K M, Lu T. Global optimization algorithm for solving linear multiplicative programming problems [J]. Optimization, 2022, 71(6): 1-21.
[26] Shen P P, Jiao H W. Linearization method for a class of multiplicative programming with exponent [J]. Applied Mathematics and Computation, 2006, 183(1): 328-336.
[27] Jiao H W, Liu S Y, Zhao Y F. Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints [J]. Applied Mathematical Modelling, 2015, 39(23-24): 7568-7582.
[28] Konno H, Fukaishi K. A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems [J]. Journal of Global Optimization, 2000, 18(3): 283- 299.
[29] Luo H, Bai X, Lim G, et al. New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation [J]. Mathematical Programming Computation, 2019, 11(1): 119-171.
[30] Luo H, Chen S, Wu H. A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation [J]. Numerical Algorithms, 2021, 88(3): 993-1024.
[31] IBM ILOG CPLEX Optimization Studio. User’s manual for CPLEX [EB/OL]. [2023-01-10]. https://www.ibm.com/docs/en/icos/22.1.1?topic=optimizers-users-manual-cplex.

线性乘积和规划问题的基于D.C.松弛的分支定界算法

A D.C. relaxation based branch-and-bound algorithm for sum-of-linear-products programming problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	孙鑫, 葛冬冬, 付德生, 魏志伟, 董丰莲, 潘师畅. 针对炼油厂系统性运营优化问题的混合分布递归及分支定界算法[J]. 运筹学学报（中英文）, 2025, 29(4): 141-158.
[2]	马素霞, 高岳林, 林洪伟, 张博. 一种新的全局优化无参数填充函数方法[J]. 运筹学学报（中英文）, 2025, 29(2): 141-157.
[3]	袁柳洋, 汤梦瑶, 迟晓妮. 一类新的无参数的填充打洞函数法[J]. 运筹学学报（中英文）, 2025, 29(2): 214-220.
[4]	白富生, 兰秘. 带隐藏约束昂贵黑箱问题的自适应代理优化方法[J]. 运筹学学报（中英文）, 2024, 28(1): 89-100.
[5]	于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法[J]. 运筹学学报, 2023, 27(1): 115-126.
[6]	黄小利, 高岳林, 张博, 刘霞. 一种求解二次约束二次规划问题的自适应全局优化算法[J]. 运筹学学报, 2022, 26(2): 83-100.
[7]	白富生, 冯丹, 张柯. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法[J]. 运筹学学报, 2021, 25(2): 1-14.
[8]	陈佳利, 张莹, 王胜刚, 谢笑盈. 一个新的填充函数及其在数据拟合问题中的应用[J]. 运筹学学报, 2021, 25(1): 81-88.
[9]	赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24(4): 63-73.
[10]	任烨权, 白延琴, 李倩, 余长君, 张连生. 一个求解池化问题的二阶锥逼近算法[J]. 运筹学学报, 2020, 24(2): 61-72.
[11]	陈永, 王薇, 徐以汎. 具有间断扩散性质的线性约束全局优化随机算法[J]. 运筹学学报, 2020, 24(1): 88-100.
[12]	王伟祥, 尚有林, 王朵. 求解带箱子集约束的非光滑全局优化问题的填充函数方法[J]. 运筹学学报, 2019, 23(1): 28-34.
[13]	蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30.
[14]	郑跃, 庄道元, 万仲平. 求解弱线性双层规划问题的一种全局优化方法[J]. 运筹学学报, 2017, 21(3): 86-94.
[15]	石礼堂, 陈伟. 非线性无约束优化问题的滤子填充函数算法[J]. 运筹学学报, 2017, 21(1): 55-64.