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.
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}