中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 4: 159 - 174

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.04.013

Research Article

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

  • Bo ZHANG ,
  • Hongyu WANG ,
  • Yuelin GAO
Expand
  • 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 date: 2022-09-10

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.013

References

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.
Options
Outlines

/

〈 〉