A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems (Q5928429)

The authors suggest a branch-and-bound algorithm for solving nonconvex optimization problems, the set of feasible solutions of which is a convex polytope \(X\) in \(n\)-dimensional Euclidean space \(\mathbb{R}^n\); the objective function of these problems has one of the following forms: \[ \sum^p_{j =1} (c_j^Tx+c_{j0}) (d^T_jx+d_{j0}) \tag{1} \] \[ \sum^p_{j=1} (c_j^Tx+ c_{j0})/ (d_j^T x+d_{j0}) \tag{2} \] where \(c_j,d_j,x\in R^n,c_{j0}, d_{j0}\) are given real numbers and \(p\) is supposed to be low. It is necessary to find \(x\in X\), which minimizes (1) or (2) over \(X\). The problem of minimizing (1) subject to \(x\in X\) is called rank-\(p\) linear multiplicative programming problem, the problem of minimizing (2) subject to \(x\in X\) is called rank-\(p\) linear fractional programming problem. The branch-and-bound algorithm for solving these problems is described and experience with computational experiments is presented.