<p>We consider the problem of minimizing the sum of affine fractional functions (SAFF) over polyhedra. Initially, we transform problem (SAFF) into an equivalent problem, and proceed to construct its relaxation and enhanced relaxation. Then, we propose a novel spatial branching rule (SBR) and integrate it with the relaxations, resulting in a spatial branching and cutting algorithm. The proposed algorithm guarantees that in each iteration, the computed optimal solution of the relaxation problem corresponding to the minimum lower bound of the optimal value of problem (SAFF) is cut off. Furthermore, we analyze the convergence and complexity of the constructed algorithm. The numerical experiments validate the effectiveness of the proposed algorithm.</p>

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

A spatial branching and cutting algorithm for minimizing the sum of affine fractional functions

  • Yaping Deng,
  • Peiping Shen

摘要

We consider the problem of minimizing the sum of affine fractional functions (SAFF) over polyhedra. Initially, we transform problem (SAFF) into an equivalent problem, and proceed to construct its relaxation and enhanced relaxation. Then, we propose a novel spatial branching rule (SBR) and integrate it with the relaxations, resulting in a spatial branching and cutting algorithm. The proposed algorithm guarantees that in each iteration, the computed optimal solution of the relaxation problem corresponding to the minimum lower bound of the optimal value of problem (SAFF) is cut off. Furthermore, we analyze the convergence and complexity of the constructed algorithm. The numerical experiments validate the effectiveness of the proposed algorithm.