一类线性乘积和规划问题的分支定界缩减方法

A Branch and Bound Reduction Algorithm for Solving a Class of Sums of Linear Multiplicative Programming Problems

摘要: 本文考虑一类带有符号的线性乘积和规划问题。利用二级松弛技术，得到原问题中目标函数的一个新的下逼近函数，进而将原来的非凸规划问题转化为一系列的线性规划问题。进一步，采用超矩形的缩减技术提出了确定此类问题全局最优值下界的分支定界缩减方法。最后，通过数值算例验证了本文所给算法的可行性与有效性。

Abstract: In this paper, we consider a class of sums of linear multiplicative programming problems. Using two-stage relaxation technique, a new lower bound of the objective function is obtained. If so, we only solve a sequence of linear programming problems. Moreover, we use a rectangular reduction strategy to provide a new branch and bound reduction algorithm for determining the lower bound of global optimal value. Numerical examples are given to illustrate the obtained results.