<p>In this paper, we consider a type of affine multiplicative programming (AMP) problem with exponents, which is known to be NP-hard. We initially transform AMP into an equivalent problem (EP) by the logarithmic transformation and the introduction of auxiliary variables. Utilizing a piecewise linear technique, we then develop a mixed-integer linear programming (MILP) relaxation to determine a lower bound for the optimal value of EP. In addition, we propose a successive linear optimization (SLO) method that converges to a KKT point of EP, thereby tightening the upper bound to the optimum of EP. Also, a rectangular contraction rule is introduced to eliminate regions that do not contain the optimal solution of AMP. By combining the MILP relaxation, the SLO method and the rectangular contraction rule, we formulate a new branch-and-bound algorithm for solving EP. Moreover, the convergence and the maximum number of iterations for the algorithm are presented. Finally, numerical experiments are conducted to verify the effectiveness and feasibility of the constructed algorithm.</p>

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

A new branch-and-bound algorithm for generalized affine multiplicative programming

  • Yaping Deng,
  • Peiping Shen

摘要

In this paper, we consider a type of affine multiplicative programming (AMP) problem with exponents, which is known to be NP-hard. We initially transform AMP into an equivalent problem (EP) by the logarithmic transformation and the introduction of auxiliary variables. Utilizing a piecewise linear technique, we then develop a mixed-integer linear programming (MILP) relaxation to determine a lower bound for the optimal value of EP. In addition, we propose a successive linear optimization (SLO) method that converges to a KKT point of EP, thereby tightening the upper bound to the optimum of EP. Also, a rectangular contraction rule is introduced to eliminate regions that do not contain the optimal solution of AMP. By combining the MILP relaxation, the SLO method and the rectangular contraction rule, we formulate a new branch-and-bound algorithm for solving EP. Moreover, the convergence and the maximum number of iterations for the algorithm are presented. Finally, numerical experiments are conducted to verify the effectiveness and feasibility of the constructed algorithm.