Multiplicative programs in the form of maximization and/or minimization have numerous applications in conservation planning, game theory, and multi-objective optimization settings. In practice, multiplicative programs are challenging to solve because of their multiplicative objective function (a product of continuous or integer variables). These challenges are twofold: 1. As the number of factors in the objective increases, so does the solution time, and the problems become computationally expensive to solve. 2. If all factors are in (0,1) or in (1,infinity), the objective may cause ill-conditioning and numerical instability. The solution methods proposed in this paper help overcome both of these challenges. The main idea is to binary-encode the multiplication operation analogously to how a computer conducts it internally. This not only solves the aforementioned numerical issues but also allows us to develop a new family of solution methods for multiplicative programs. One such method is to solve the multiplicative programs bit-by-bit, i.e., iteratively computing the optimal value of each bit of the objective function. In an extensive computational study, we explore a number of solution methods that solve multiplicative programs faster and more accurately.
Article
View Solving Multiplicative Programs by Binary-encoding the Multiplication Operation