<p>In this paper, an efficient branch and bound algorithm with a new adjustable branching rule is presented to solve the sum of linear ratios problem (SLRP). In the algorithm, problem (SLRP) is first converted into its equivalent form (ERP) whose objective function involves (<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10589_2025_679_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(p-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>) linear ratios via Charnes–Cooper transformation, and (ERP) is equivalently translated to problem (EP) which has a linear objective function by some variables transformation. A convex relaxation problem (CRP) for (EP) is constructed to obtain a lower bound to the optimal value of (EP). In addition, a novel adjustable branching rule is proposed to offer tight lower bounds to the optimal values of (EP) over the corresponding sub-rectangles under some certain conditions. Also, a convex combination method is designed to update the upper bound for the optimal value of (ERP). By continuously refining the initial rectangle and tackling a series of convex relaxation problems, the presented algorithm can find a global optimal solution to (ERP). Moreover, we analyze the complexity result of the proposed algorithm. Finally, the feasibility and effectiveness of the algorithm are verified by preliminary numerical experiments.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An efficient global optimization algorithm for the sum of linear ratios problems based on a novel adjustable branching rule

  • Bingdi Huang,
  • Peiping Shen

摘要

In this paper, an efficient branch and bound algorithm with a new adjustable branching rule is presented to solve the sum of linear ratios problem (SLRP). In the algorithm, problem (SLRP) is first converted into its equivalent form (ERP) whose objective function involves ( \(p-1\) p - 1 ) linear ratios via Charnes–Cooper transformation, and (ERP) is equivalently translated to problem (EP) which has a linear objective function by some variables transformation. A convex relaxation problem (CRP) for (EP) is constructed to obtain a lower bound to the optimal value of (EP). In addition, a novel adjustable branching rule is proposed to offer tight lower bounds to the optimal values of (EP) over the corresponding sub-rectangles under some certain conditions. Also, a convex combination method is designed to update the upper bound for the optimal value of (ERP). By continuously refining the initial rectangle and tackling a series of convex relaxation problems, the presented algorithm can find a global optimal solution to (ERP). Moreover, we analyze the complexity result of the proposed algorithm. Finally, the feasibility and effectiveness of the algorithm are verified by preliminary numerical experiments.