Optimization Online


Solving Multiplicative Programs by Binary-encoding the Multiplication Operation

Payman Ghasemi Saghand(payman***at***usf.edu)
Fabian Rigterink(fabian.rigterink***at***exxonmobil.com)
Vahid Mahmoodian(mahmoodian***at***usf.edu)
Hadi Charkhgard(hcharkhgard***at***usf.edu)

Abstract: 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.

Keywords: Multiplicative program; Binary-encoding; Multi-linear optimization, Mixed integer second order cone programming, Nonconvex nonlinear programming

Category 1: Applications -- OR and Management Sciences

Category 2: Other Topics (Game Theory )


Download: [PDF]

Entry Submitted: 01/06/2021
Entry Accepted: 01/06/2021
Entry Last Modified: 01/06/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society