Exact solution approaches for integer linear generalized maximum multiplicative programs through the lens of multi-objective optimization. (English) Zbl 1511.90382
Summary: We study a class of single-objective non-linear 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 conservation 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 finite number of single-objective integer linear programs to compute an optimal solution of an IL-GMMP (which is nonlinear). 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.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90C05 | Linear programming |
| 90C10 | Integer programming |
| 90C11 | Mixed integer programming |
| 91A12 | Cooperative games |
Keywords:
multi-objective integer linear programming; generalized maximum multiplicative programming; Nash social welfare; Nash bargaining solution; geometric mean optimizationReferences:
| [1] | Ardakan, M. A.; Hamadani, A. Z., Reliability optimization of series-parallel systems with mixed redundancy strategy in subsystems, Reliab. Eng. Syst. Saf., 130, 132-139 (2014) |
| [2] | Ben-Tal, A.; Nemirovski, A., On polyhedral approximations of the second-order cone, Math. Oper. Res., 26, 2, 193-205 (2001) · Zbl 1082.90133 |
| [3] | Benson, H. P., Optimization over the efficient set, J. Math. Anal. Appl., 98, 2, 562-580 (1984) · Zbl 0534.90077 |
| [4] | Boland, N.; Charkhgard, H.; Savelsbergh, M., A new method for optimizing a linear function over the efficient set of a multiobjective integer program, European J. Oper. Res., 260, 3, 904-919 (2017) · Zbl 1403.90594 |
| [5] | Calkin, D. E.; Montgomery, C. A.; Schumaker, N. H.; Polasky, S.; Arthur, J. L.; Nalle, D. J., Developing a production possibility set of wildlife species persistence and timber harvest value, Can. J. Forest Res., 32, 8, 1329-1342 (2002) |
| [6] | Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; Wang, J., The unreasonable fairness of maximum Nash welfare, (Proceedings of the 2016 ACM Conference on Economics and Computation. Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16 (2016), ACM: ACM New York, NY, USA), 305-322, URL http://doi.acm.org/10.1145/2940716.2940726 |
| [7] | Chakrabarty, D.; Devanur, N.; Vazirani, V. V., New results on rationality and strongly polynomial time solvability in eisenberg-gale markets, (Internet and Network Economics. Internet and Network Economics, Lecture Notes in Computer Science, vol. 4286 (2006), Springer Berlin Heidelberg), 239-250 |
| [8] | Charkhgard, H.; Keshanian, K.; Esmaeilbeigi, R.; Charkhgard, P., The magic of Nash social welfare in optimization: Do not sum, just multiply (2020), Preprint. URL https://doi.org/10.13140/RG.2.2.31498.21440/1 |
| [9] | Charkhgard, H.; Savelsbergh, M.; Talebian, M., A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints, Comput. Oper. Res., 89, 17-30 (2018) · Zbl 1391.90406 |
| [10] | Coit, D. W., Cold-standby redundancy optimization for nonrepairable systems, IIE Trans., 33, 6, 471-478 (2001) |
| [11] | Cole, R.; Gkatzelis, V., Approximating the Nash social welfare with indivisible items, (Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15 (2015), ACM: ACM New York, NY, USA), 371-380, URL http://doi.acm.org/10.1145/2746539.2746589 · Zbl 1322.91030 |
| [12] | Conley, J. P.; Wilkie, S., The bargaining problem without convexity: Extending the egalitarian and Kalai-Smorodinsky solutions, Econom. Lett., 36, 4, 365-369 (1991) · Zbl 0758.90089 |
| [13] | Darmann, A.; Schauer, J., Maximizing Nash product social welfare in allocating indivisible goods, European J. Oper. Res., 247, 2, 548-559 (2015), URL http://www.sciencedirect.com/science/article/pii/S037722171500483X · Zbl 1346.91109 |
| [14] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 |
| [15] | Ehrgott, M., Multicriteria Optimization (2005), Springer: Springer New York · Zbl 1132.90001 |
| [16] | Eisenberg, E.; Gale, D., Consensus of subjective probabilities: The pari-mutuel method, Ann. Math. Stat., 30, 1, 165-168 (1959) · Zbl 0087.13805 |
| [17] | Engau, A.; Wiecek, M. M., Interactive coordination of objective decompositions in multiobjective programming, Manage. Sci., 54, 7, 1350-1363 (2008) · Zbl 1232.90327 |
| [18] | Erlebach, T.; Kellerer, H.; Pferschy, U., Approximating multiobjective knapsack problems, Manage. Sci., 48, 12, 1603-1612 (2002) · Zbl 1232.90324 |
| [19] | Fain, B.; Munagala, K.; Shah, N., Fair allocation of indivisible public goods, (Proceedings of the 2018 ACM Conference on Economics and Computation. Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18 (2018), ACM: ACM New York, NY, USA), 575-592, URL http://doi.acm.org/10.1145/3219166.3219174 |
| [20] | Feizabadi, M.; Jahromi, A. E., A new model for reliability optimization of series-parallel systems with non-homogeneous components, Reliab. Eng. Syst. Saf., 157, 101-112 (2017) |
| [21] | Fernandez-Antolin, A.; Lurkin, V.; de Lapparent, M.; Bierlaire, M., Discrete-continuous maximum likelihood for the estimation of nested logit models, (16th Swiss Transport Research Conference. 16th Swiss Transport Research Conference, Ascona, Switzerland, 17-19 May (2017)), URL http://infoscience.epfl.ch/record/229178 |
| [22] | Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 1, 91-104 (2005) · Zbl 1077.90039 |
| [23] | Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 1, 23-47 (2003) · Zbl 1060.90056 |
| [24] | Gao, Y.; Xu, C.; Yang, Y., An outcome-space finite algorithm for solving linear multiplicative programming, Appl. Math. Comput., 179, 2, 494-505 (2006) · Zbl 1103.65065 |
| [25] | Grötschel, M.; Lovasz, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0634.05001 |
| [26] | Haider, Z.; Charkhgard, H.; Kwon, C., A robust optimization approach for solving problems in conservation planning, Ecol. Model., 368, 288-297 (2018) |
| [27] | Hamming, R. W., Error detecting and error correcting codes, Bell Syst. Tech. J., 29, 2, 147-160 (1950) · Zbl 1402.94084 |
| [28] | Hensher, D. A., Sequential and full information maximum likelihood estimation of a nested logit model, Rev. Econ. Stat., 68, 4, 657-667 (1986) |
| [29] | Hooker, J., Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Vol. 2 (2011), John Wiley & Sons |
| [30] | IBM ILOG CPLEX Optimization Studio, J., CPLEX Parameters reference, 25 (2016), URL https://goo.gl/Fv5R2Z |
| [31] | Jain, K.; Vazirani, V. V., Eisenberg-gale markets: Algorithms and structural properties, (Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07 (2007), ACM: ACM New York, NY, USA), 364-373 · Zbl 1232.91452 |
| [32] | Johnson, M. P.; Hurter, A. P., Decision support for a housing mobility program using a multiobjective optimization model, Manage. Sci., 46, 12, 1569-1584 (2000) · Zbl 1232.90283 |
| [33] | Jorge, J. M., An algorithm for optimizing a linear function over an integer efficient set, European J. Oper. Res., 195, 1, 98-103 (2009) · Zbl 1161.90443 |
| [34] | Kalai, E., Nonsymmetric Nash solutions and replications of 2-person bargaining, Internat. J. Game Theory, 6, 3, 129-133 (1977) · Zbl 0371.90134 |
| [35] | Kaneko, M.; Nakamura, K., The Nash social welfare function, Econometrica, 47, 2, 423-435 (1979) · Zbl 0431.90091 |
| [36] | Mahmoodian, V.; Charkhgard, H.; Zhang, Y., Multi-objective optimization based algorithms for solving mixed integer linear minimum multiplicative programs, Comput. Oper. Res., 128, Article 105178 pp. (2021) · Zbl 1510.90251 |
| [37] | Mendoza-Alonzo, J.; Zayas-Castro, J.; Charkhgard, H., Office-based and home-care for older adults in primary care: A comparative analysis using the Nash bargaining solution, Soc.-Econ. Plann. Sci., Article 100710 pp. (2019), URL http://www.sciencedirect.com/science/article/pii/S0038012118303203 |
| [38] | Nash, J. F., The bargaining problem, Econometrica, 18, 155-162 (1950) · Zbl 1202.91122 |
| [39] | Nash, J. F., Two-person cooperative games, Econometrica, 21, 128-140 (1953) · Zbl 0050.14102 |
| [40] | Nguyen, T. T.; Rothe, J., Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods, Discrete Appl. Math., 179, 54-68 (2014), URL http://www.sciencedirect.com/science/article/pii/S0166218X14004120 · Zbl 1307.91107 |
| [41] | Nicholson, E.; Possingham, H. P., Objectives for multiple-species conservation planning, Conserv. Biol., 20, 3, 871-881 (2006) |
| [42] | Nicholson, E.; Possingham, H. P., Objectives for multiple-species conservation planning, Conserv. Biol., 20, 3, 871-881 (2006) |
| [43] | Özpeynirci, O.; Köksalan, M., An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs, Manage. Sci., 56, 12, 2302-2315 (2010) · Zbl 1232.90329 |
| [44] | Phelps, S. P.; Köksalan, M., An interactive evolutionary metaheuristic for multiobjective combinatorial optimization, Manage. Sci., 49, 12, 1726-1738 (2003) · Zbl 1232.90330 |
| [45] | Rao, S., Game theory approach for multiobjective structural optimization, Comput. Struct., 25, 1, 119-127 (1987) · Zbl 0597.73093 |
| [46] | Retal, S.; Idrissi, A., A multi-objective optimization system for mobile gateways selection in vehicular Ad-Hoc networks, Comput. Electr. Eng., 73, 289-303 (2019), URL http://www.sciencedirect.com/science/article/pii/S0045790617336728 |
| [47] | Ryoo, H.-S.; Sahinidis, N. V., Global optimization of multiplicative programs, J. Global Optim., 26, 4, 387-418 (2003) · Zbl 1052.90091 |
| [48] | Saghand, P. G.; Charkhgard, H., A criterion space search algorithm for mixed integer linear maximum multiplicative programs: a multiobjective optimization approach, Int. Trans. Oper. Res. (2021), Available online |
| [49] | Saghand, P. G.; Charkhgard, H.; Kwon, C., A branch-and-bound algorithm for a class of mixed integer linear maximum multiplicative programs: A bi-objective optimization approach, Comput. Oper. Res., 101, 263-274 (2019) · Zbl 1458.90573 |
| [50] | Sayın, S., Optimizing over the efficient set using a top-down search of faces, Oper. Res., 48, 1, 65-72 (2000) · Zbl 1106.90376 |
| [51] | Sayın, S.; Kouvelis, P., The multiobjective discrete optimization problem: A weighted min-max two-stage optimization approach and a bicriteria algorithm, Manage. Sci., 51, 10, 1572-1581 (2005) · Zbl 1232.90331 |
| [52] | Serrano, R., Fifty years of the Nash program 1953-2003, Invest. Econ., 219-258 (2005) |
| [53] | Shao, L.; Ehrgott, M., An objective space cut and bound algorithm for convex multiplicative programmes, J. Global Optim., 58, 4, 711-728 (2014) · Zbl 1298.90081 |
| [54] | Shao, L.; Ehrgott, M., Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes, Optimization, 65, 2, 415-431 (2016) · Zbl 1370.90254 |
| [55] | Sierra Altamiranda, A.; Charkhgard, H., A new exact algorithm to optimize a linear function over the set of efficient solutions for biobjective mixed integer linear programs, INFORMS J. Comput., 31, 4, 823-840 (2019) · Zbl 1528.90237 |
| [56] | Sierra-Altamiranda, A.; Charkhgard, H.; Eaton, M.; Martin, J.; Yurek, S.; Udell, B. J., Spatial conservation planning under uncertainty using modern portfolio theory and Nash bargaining solution, Ecol. Model., 423, Article 109016 pp. (2020), URL http://www.sciencedirect.com/science/article/pii/S0304380020300880 |
| [57] | Steele, J. M., The Cauchy-Schwarz Master Class: an Introduction to the Art of Mathematical Inequalities, 19-28 (2004), Cambridge University Press · Zbl 1060.26023 |
| [58] | Stidsen, T.; Andersen, K. A.; Dammann, B., A branch and bound algorithm for a class of biobjective mixed integer programs, Manage. Sci., 60, 4, 1009-1032 (2014) |
| [59] | Vazirani, V. V., Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games, SIAM J. Discrete Math., 26(3), 896-918 (2012) · Zbl 1258.68189 |
| [60] | Wallenius, J.; Dyer, J. S.; Fishburn, P. C.; Steuer, R. E.; Zionts, S.; Deb, K., Multiple criteria decision making, multiattribute utility theory: Recent accomplishments and what Lies ahead, Manage. Sci., 54, 7, 1336-1349 (2008) · Zbl 1232.90228 |
| [61] | Williams, P. H.; Araújo, M. B., Apples, oranges, and probabilities: Integrating multiple factors into biodiversity conservation with consistency, Environ. Model. Assess., 7, 2, 139-151 (2002) |
| [62] | Zhang, D., A logic-based axiomatic model of bargaining, Artificial Intelligence, 174, 16, 1307-1322 (2010) · Zbl 1237.91122 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
