-

 

 

 




Optimization Online





 

Exact Solution Approaches for Integer Linear Generalized Maximum Multiplicative Programs Through the Lens of Multi-objective Optimization

Payman Ghasemi Saghand(payman***at***mail.usf.edu)
Hadi Charkhgard(hcharkhgard***at***usf.edu)

Abstract: We study a class of single-objective nonlinear optimization problems, the so-called Integer Linear Generalized Maximum Multiplicative Programs (IL-GMMP). This class of optimization problems has a significant number of applications in different fields of study including but not limited to game theory, systems reliability, and conservative planning. An IL-GMMP can be reformulated as a mixed integer Second-Order Cone Program (SOCP) and therefore, can be solved effectively by commercial solvers such as IBM ILOG CPLEX, Gurobi, and FICO Xpress. In this study, we show that IL-GMMPs can be viewed as special cases of the problem of optimization over the efficient (or Pareto-optimal) set in multi-objective integer linear programming. Based on this observation, we develop three exact solution approaches with a desirable property: they only solve a number of single-objective integer linear programs to compute an optimal solution of an IL-GMMP. Through an extensive computational study with 57600 experiments, we compare the performance of all three algorithms using the three main commercial single-objective integer linear programming solvers in the market: CPLEX, Gurobi, and Xpress. We also compare the performance of our algorithms using the mixed integer SOCP solvers of CPLEX, Gurobi, and Xpress. The results show that the choice of a commercial solver impacts the solution time dramatically and that, by the right choice of solver, one of our proposed algorithms is significantly faster than other methods. We also illustrate that although it is possible to linearize IL-GMMPs, commercial solvers struggle to solve such linearized instances.

Keywords: Multi-objective integer linear programming, Generalized maximum multiplicative programming, Criterion space search algorithms, Nash bargaining solution, Geometric mean optimization

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming

Category 3: Other Topics (Game Theory )

Citation: author={Payman Ghasemi Saghand and Hadi Charkhgard}, title={Multi-objective integer linear programming, Generalized maximum multiplicative programming, Criterion space search algorithms, Nash bargaining solution, Geometric mean optimization}, url={https://doi.org/10.13140/RG.2.2.20212.71047}

Download: [PDF]

Entry Submitted: 10/15/2019
Entry Accepted: 10/15/2019
Entry Last Modified: 10/15/2019

Modify/Update this entry


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

 

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