An efficient outcome-space branch-and-bound algorithm for solving a class of large-scale linear multiplicative programs

In this paper, we present an efficient algorithm for solving a class of large-scale linear multiplicative programs (LMPs). The problem LMP is first converted into an equivalent problem (ENP) and then a lambda-piecewise linear relaxation technique is proposed. This technique establishes a linear relaxation problem, providing a valid lower bound for the global optimal value of the ENP. This leads to the proposal of a novel outcome-space-based branch-and-bound algorithm for a class of LMPs. Meanwhile, a new region reduction technique is implemented in the outcome space to eliminate as many infeasible regions as possible. In addition, the paper provides a convergence analysis, a complexity assessment of the algorithm, and estimates the number of worst-case iterations required to attain an epsilon-optimal solution. Finally, the new algorithm is compared to state-of-the-art alternatives, demonstrating its advantages in solving large-scale LMPs.