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

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.