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

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

Abstract

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

CLC Number:

O221.2

Bo ZHANG, Hongyu WANG, Yuelin GAO. 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.

Figures/Tables 6

References 31

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	MulveyJ M,VanderbeiR J,ZeniosS 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	CambiniR,SodiniC.On the minimization of a class of generalized linear functions on a flow polytope[J].Optimization,2014,63(10):1449-1464.
5	BennettK P.Global tree optimization: A non-greedy decision tree algorithm[J].Computing Science and Statistics,1994,26(1):156-156.
6	BennettK P,MangasarianO L.Bilinear separation of two sets in n-space[J].Computational Optimization and Applications,1993,2(3):207-227.
7	MatsuiT.NP-hardness of linear multiplicative programming and related problems[J].Journal of Global Optimization,1996,9(2):113-119.
8	ShenP,HuangB.Global algorithm for solving linear multiplicative programming problems[J].Optimization Letters,2020,14(3):693-710.
9	GaoY,XuC,YangY.An outcome-space finite algorithm for solving linear multiplicative programming[J].Applied Mathematics and Computation,2006,179(2):494-505.
10	BensonH P,BogerG M.Outcome-space cutting-plane algorithm for linear multiplicative programming[J].Journal of Optimization Theory and Applications,2000,104(2):301-322.
11	WangC F,LiuS Y,ShenP P.Global minimization of a generalized linear multiplicative programming[J].Applied Mathematical Modelling,2012,36(6):2446-2451.
12	ShenP,WangK,LuT.Outer space branch and bound algorithm for solving linear multiplicative programming problems[J].Journal of Global Optimization,2020,78(3):453-482.
13	WangC F,DengY P,ShenP 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	RyooH S,SahinidisN V.Global optimization of multiplicative programs[J].Journal of Global Optimization,2003,26(4):387-418.
15	WangC F,BaiY Q,ShenP P.A practicable branch-and-bound algorithm for globally solving linear multiplicative programming[J].Optimization,2017,66(3):397-405.
16	HorstR,TuyH.Global Optimization: Deterministic Approaches[M].Deutschland:Springer Science & Business Media,2013.
17	YounessE A.Level set algorithm for solving convex multiplicative programming problems[J].Applied Mathematics and Computation,2005,167(2):1412-1417.
18	LiuS,ZhaoY.An efficient algorithm for globally solving generalized linear multiplicative programming[J].Journal of Computational and Applied Mathematics,2016,296(1):840-847.
19	FalkJ,PalocsayS.Image space analysis of generalized fractional programs[J].Journal of Global Optimization,1994,4(1):63-88.
20	KonnoH,KunoT.Linear multiplicative programming[J].Mathematical Programming,1992,56(1-3):51-64.
21	OliveiraR M,FerreiraP A V.An outcome space approach for generalized convex multiplicative programs[J].Journal of Global Optimization,2010,47(1):107-118.
22	CharkhgardH,SavelsberghM,TalebianM.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	ThuyL Q,KimN T B,ThienN 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	JiaoH,LiuS,ChenY.Global optimization algorithm for a generalized linear multiplicative programming[J].Journal of Applied Mathematics and Computing,2012,40(1):551-568.
25	ShenP P,WangK M,LuT.Global optimization algorithm for solving linear multiplicative programming problems[J].Optimization,2022,71(6):1-21.
26	ShenP P,JiaoH W.Linearization method for a class of multiplicative programming with exponent[J].Applied Mathematics and Computation,2006,183(1):328-336.
27	JiaoH W,LiuS Y,ZhaoY 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	KonnoH,FukaishiK.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	LuoH,BaiX,LimG,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	LuoH,ChenS,WuH.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.

例	方法	最优解	最优值	迭代次数	时间/s
1	文献[12]	(0, 4)	3	50	0.447 3
	文献[13]	(0, 4)	3	4	0.044 3
	DCRBBA	(0, 4)	3	3	0.037 4
2	文献[12]	(2, 8)	10	19	0.172 3
	文献[13]	(2, 8)	10	17	0.094 4
	DCRBBA	(2, 8)	10	1	0.008 9
3	文献[12]	(0, 5)	-233	63	0.768 3
	文献[13]	(0, 5)	-233	7	0.051 2
	DCRBBA	(0, 5)	-233	1	0.009 8
4	文献[12]	(0, 0)	4	25	0.283 9
	文献[13]	(0, 0)	4	1	0.019 5
	DCRBBA	(0, 0)	4	6	0.104 5
5	文献[12]	(1, 4)	-22	156	1.627 4
	文献[13]	(1, 4)	-22	1	0.008 1
	DCRBBA	(1, 4)	-22	1	0.006 7
6	文献[12]	(0, 3)	-2.5	291	2.999 4
	文献[13]	(0, 3)	-2.5	18	0.110 7
	DCRBBA	(0, 3)	-2.5	30	0.445 1
7	文献[12]	(1.316 9, 2.244 1)	4.956 6	1 829	21.265 7
	文献[13]	(1.316 9, 2.244 1)	4.956 6	14	0.186 5
	DCRBBA	(1.316 9, 2.244 1)	4.956 6	15	0.197 8
8	文献[12]	(5.555 6, 1.777 8, 2.666 7)	-112.753 1	616	7.373 6
	文献[13]	(5.555 6, 1.777 8, 2.666 7)	-112.753 1	45	0.319 3
	DCRBBA	(5.555 6, 1.777 8, 2.666 7)	-112.753 1	2	0.015 9
9	文献[12]	(1.314 8, 0.139 6, 0.0, 0.423 3)	0.890 2	15	0.130 6
	文献[13]	(1.314 8, 0.139 6, 0.0, 0.423 3)	0.890 2	35	0.216 2
	DCRBBA	(1.314 8, 0.139 6, 0.0, 0.423 3)	0.890 2	6	0.069 5

$ p $	迭代次数	最大节点数	时间/s	$ p $	迭代次数	最大节点数	时间/s
10	13.0	1.6	0.345 7	60	1 485.9	284.8	124.621 4
20	61.7	6.1	1.967 6	70	2 729.5	627.3	404.971 9
30	124.5	22.5	4.133 8	80	7 369.7	2 834.5	2 044.056 8
40	159.5	15.8	5.561 2	90	11 791.5	3 628.2	4 101.988 1
50	495.6	129.3	17.025 1	100	31 129.7	11 529.5	9 376.816 8

$ (p, m, n) $	算法DCRBBA		文献[13]中的算法		文献[12]中的算法
$ (p, m, n) $	迭代次数	时间/s	迭代次数	时间/s	迭代次数	时间/s
(2, 30, 30)	4.0	0.118 2	139.2	1.678 5	29.6	0.274 3
(2, 40, 40)	7.3	0.197 7	548.5	7.512 6	28.0	0.325 9
(2, 100, 100)	3.2	0.529 0	34 868.4	718.818 4	17.9	1.416 4
(2, 100, 200)	5.8	2.128 5	48 469.1	1 530.544 3	46.7	5.039 6
(2, 100, 300)	4.5	3.450 7	—	—	38.1	5.915 4
(2, 300, 300)	3.0	7.498 7	—	—	13.9	20.554 8
(3, 30, 30)	6.9	0.176 5	403.8	4.419 6	125.7	1.204 8
(3, 40, 40)	7.5	0.251 0	252.1	3.397 0	67.7	0.801 2
(3, 100, 100)	6.8	1.196 1	3 925.8	64.317 4	61.0	4.517 7
(3, 100, 200)	10.3	3.908 9	31 073.9	959.202 5	152.5	17.108 2
(3, 100, 300)	8.6	1.524 9	—	—	198.4	31.601 8
(3, 300, 300)	5.8	7.242 5	—	—	36.2	66.255 4
(4, 30, 30)	14.6	0.420 1	403.1	4.530 5	504.6	11.014 7
(4, 40, 40)	17.6	0.586 6	667.2	9.342 4	2 325.6	53.322 6
(4, 100, 100)	10.7	0.663 7	1 501.0	27.086 2	85.0	5.973 5
(4, 100, 200)	16.2	1.638 2	43 682.2	1 381.898 8	682.5	76.599 1
(5, 30, 30)	26.4	0.803 4	266.9	3.292 9	558.7	12.100 7
(5, 40, 40)	18.7	0.662 2	491.1	7.877 9	536.4	13.971 1
(5, 100, 100)	23.8	1.421 5	4 056.8	71.662 9	416.0	29.826 1
(7, 30, 30)	62.5	2.136 7	424.8	4.888 2	15 530.4	317.040 7
(7, 40, 40)	45.8	1.930 7	400.6	6.021 2	902.2	17.939 1
(7, 100, 100)	37.2	2.220 2	2 326.3	42.471 0	2 051.4	148.069 4
(10, 30, 30)	136.9	5.147 6	333.3	4.446 3	10 916.9	186.163 9
(10, 40, 40)	94.4	4.544 1	371.9	5.701 0	11 007.2	320.768 1
(10, 100, 100)	79.0	4.969 9	1 443.0	27.580 1	6 874.6	516.006 4
(10, 100, 300)	380.7	59.050 2	—	—	8 397.9	1 551.552 3

$ (p, m, n) $	算法DCRBBA			文献[13]中的算法
$ (p, m, n) $	迭代次数	时间/s	最优值	迭代次数	时间/s	最优值
(20, 10, 10)	187.3	3.958 7	—0.347 1	20.7	0.187 6	—0.347 1
(30, 10, 10)	250.4	5.124 3	—0.509 2	24.3	0.220 5	—0.509 1
(40, 10, 10)	436.9	10.996 6	—0.372 9	36.5	0.275 8	—0.372 9
(20, 20, 20)	252.7	4.797 0	—0.116 7	90.4	0.616 7	—0.115 3
(30, 20, 20)	607.1	13.811 2	—0.244 7	102.9	0.757 3	—0.243 7
(20, 30, 30)	610.4	13.650 9	0.101 7	193.2	1.480 2	0.103 2
(30, 30, 30)	13 230.0	391.176 7	—0.124 3	662.5	5.527 9	—0.124 1

$ (p, m, n) $	迭代次数	时间/s	最优值	$ (p, m, n) $	迭代次数	时间/s	最优值
(2, 100, 500)	5.5	1.680 0	—0.072 7	(4, 100, 1 000)	19.5	25.654 2	—0.117 0
(2, 100, 700)	5.1	2.620 3	—0.069 5	(4, 100, 3 000)	21.0	327.761 9	0.000 7
(2, 100, 1 000)	5.0	5.159 2	—0.009 7	(4, 100, 5 000)	21.4	931.719 4	—0.050 9
(2, 100, 3 000)	6.5	99.546 4	—0.033 8	(5, 100, 500)	23.3	5.449 0	—0.040 3
(2, 100, 5 000)	6.6	510.690 5	—0.068 3	(5, 100, 700)	26.4	10.287 7	—0.109 3
(3, 100, 500)	9.8	3.403 5	—0.089 3	(5, 100, 1 000)	30.0	24.112 9	—0.040 1
(3, 100, 700)	11.0	6.746 9	0.093 0	(5, 100, 3 000)	39.3	421.903 8	—0.127 1
(3, 100, 1 000)	10.4	14.623 1	—0.022 3	(7, 100, 500)	66.4	14.785 0	—0.076 7
(3, 100, 3 000)	13.8	251.658 2	—0.118 0	(7, 100, 700)	70.6	27.189 0	—0.241 7
(3, 100, 5 000)	12.9	965.636 6	—0.045 5	(7, 100, 1 000)	84.4	66.218 9	—0.102 3
(4, 100, 500)	19.2	6.557 2	0.090 8	(10, 100, 500)	402.9	87.011 8	0.024 9
(4, 100, 700)	17.9	10.511 3	—0.123 9	(10, 100, 1 000)	384.2	285.929 0	—0.162 9

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 31

Related Articles 15

Recommended Articles

Metrics

Comments

$ (p, m, n) $	DCRBBA		EDCRBBA		ADMBB
$ (p, m, n) $	迭代次数	时间/s	迭代次数	时间/s	迭代次数	时间/s
(3, 20, 100)	19.8	0.558 3	15.6	0.478 9	18.5	0.272 8
(3, 30, 150)	23.1	0.968 8	16.5	0.676 0	20.2	0.401 4
(3, 40, 200)	19.6	1.167 9	12.5	0.703 1	16.8	0.466 1
(5, 20, 100)	66.8	2.253 8	54.5	1.820 8	69.3	1.208 0
(5, 30, 150)	94.2	4.416 0	58.6	2.741 4	76.3	1.811 6
(5, 40, 200)	54.3	3.593 1	31.2	1.998 6	40.0	1.292 0
(7, 20, 100)	162.6	5.989 3	99.8	3.682 7	114.0	2.167 3
(7, 30, 150)	124.3	6.400 5	61.0	3.104 6	67.1	1.764 8
(7, 40, 200)	162.2	12.253 6	79.2	5.904 1	103.4	3.924 7
(10, 20, 100)	605.1	24.124 1	324.4	13.094 8	371.4	7.615 4
(10, 30, 150)	995.1	59.328 4	363.2	21.865 7	454.7	14.058 7
(10, 40, 200)	1 520.4	135.841 2	677.6	59.932 9	815.4	36.606 3

[1]	Xin SUN, Dongdong GE, Desheng FU, Zhiwei WEI, Fenglian DONG, Shichang PAN. A hybrid distribution recursion and branch and bound algorithm for Petroluem refinery optimization problem [J]. Operations Research Transactions, 2025, 29(4): 141-158.
[2]	Suxia MA, Yuelin GAO, Hongwei LIN, Bo ZHANG. A new non parameter-filled function method for global optimization [J]. Operations Research Transactions, 2025, 29(2): 141-157.
[3]	Liuyang YUAN, Mengyao TANG, Xiaoni CHI. A new class of parameter-free filled tunnel function methods [J]. Operations Research Transactions, 2025, 29(2): 214-220.
[4]	Fusheng BAI, Mi LAN. An adaptive surrogate optimization method for expensive black-box problems with hidden constraints [J]. Operations Research Transactions, 2024, 28(1): 89-100.
[5]	Jing YU, Zhe XU, Fang XIE. A branch and bound method for project scheduling problem with activities overlapping [J]. Operations Research Transactions, 2023, 27(1): 115-126.
[6]	Xiaoli HUANG, Yuelin GAO, Bo ZHANG, Xia LIU. An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems [J]. Operations Research Transactions, 2022, 26(2): 83-100.
[7]	Fusheng BAI, Dan FENG, Ke ZHANG. Combined response surface method with adaptive sampling for expensive black-box global optimization [J]. Operations Research Transactions, 2021, 25(2): 1-14.
[8]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[9]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[10]	ZHAO Dan, GAO Yuelin. Non-parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2020, 24(4): 63-73.
[11]	CHEN Yong, WANG Wei, XU Yifan. An stochastic algorithm for global optimization with linear constraints based on intermittent diffusion [J]. Operations Research Transactions, 2020, 24(1): 88-100.
[12]	WANG Weixiang, SHANG Youlin, WANG Duo. Filled function method for solving non-smooth box constrained global optimization problems [J]. Operations Research Transactions, 2019, 23(1): 28-34.
[13]	TIAN Mingyu, YANG Yongjian. A global optimization algorithm for polynomial programming [J]. Operations Research Transactions, 2018, 22(4): 79-88.
[14]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[15]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.