×
Ghasemi Saghand, Payman; Charkhgard, Hadi

A criterion space search algorithm for mixed integer linear maximum multiplicative programs: a multiobjective optimization approach. (English) Zbl 07771173

Int. Trans. Oper. Res. 29, No. 3, 1659-1687 (2022).
Summary: We study a class of mixed integer optimization problems with linear constraints and a multilinear objective function, the so-called mixed integer linear maximum multiplicative programs (MIL-MMPs). Such a problem can be transformed into a second-order cone program (SOCP) and can be solved effectively by a commercial solver such as CPLEX. However, MIL-MMPs can also be viewed as special cases of the problem of optimization over the set of efficient solutions in multiobjective optimization. Using this observation, we develop a criterion space search algorithm for solving any MIL-MMP. An extensive computational study on around 2000 instances illustrates that the proposed algorithm significantly outperforms not only the CPLEX mixed integer SOCP solver but also a state-of-the-art algorithm that is capable of solving special cases of MIL-MMPs. Moreover, the computational study illustrates that even if we linearize the objective function and solve the linearized problem by CPLEX, the proposed algorithm still performs significantly better.
{© 2021 The Authors. International Transactions in Operational Research © 2021 International Federation of Operational Research Societies}

Cited in 3 Documents

MSC:

90-XX Operations research, mathematical programming

Keywords:

mixed integer maximum multiplicative programming; multiobjective optimization; optimization over the efficient set; criterion space search algorithm

Software:

CPLEX
Cite Review PDF
Full Text: DOI

References:

[1] Ardakan, M.A., Hamadani, A.Z., 2014. Reliability optimization of series‐parallel systems with mixed redundancy strategy in subsystems. Reliability Engineering & System Safety130, 132-139.
[2] Benson, H., Boger, G., 1997. Multiplicative programming problems: analysis and efficient point search heuristic. Journal of Optimization Theory and Applications94, 2, 487-510. · Zbl 0889.90128
[3] Benson, H.P., 1984. Optimization over the efficient set. Journal of Mathematical Analysis and Applications98, 2, 562-580. · Zbl 0534.90077
[4] Ben‐Tal, A., Nemirovski, A., 2001. On polyhedral approximations of the second‐order cone. Mathematics of Operations Research26, 2, 193-205. · Zbl 1082.90133
[5] Boland, N., Charkhgard, H., Savelsbergh, M., 2015. A criterion space search algorithm for biobjective mixed integer programming: the triangle splitting method. INFORMS Journal on Computing27, 4, 597-618. · Zbl 1338.90364
[6] Boland, N., Charkhgard, H., Savelsbergh, M., 2017a. A new method for optimizing a linear function over the efficient set of a multiobjective integer program. European Journal of Operational Research260, 3, 904-919. · Zbl 1403.90594
[7] Boland, N., Charkhgard, H., Savelsbergh, M., 2017b. The quadrant shrinking method: a simple and efficient algorithm for solving tri‐objective integer programs. European Journal of Operational Research260, 3, 873-885. · Zbl 1403.90593
[8] Bozkurt, B., Fowler, J.W., Gel, E.S., Kim, B., Köksalan, M., Wallenius, J., 2010. Quantitative comparison of approximate solution sets for multicriteria optimization problems with weighted Tchebycheff preference function. Operations Research58, 3, 650-659. · Zbl 1228.90105
[9] Calkin, D.E., Montgomery, C.A., Schumaker, N.H., Polasky, S., Arthur, J.L., Nalle, D.J., 2002. Developing a production possibility set of wildlife species persistence and timber harvest value. Canadian Journal of Forest Research32, 8, 1329-1342.
[10] Chakrabarty, D., Devanur, N., Vazirani, V.V., 2006. New results on rationality and strongly polynomial time solvability in Eisenberg-Gale markets. In Spirakis, P. (ed.), Mavronicolas, M. (ed.), Kontogiannis, S. (ed.) (eds) Internet and Network Economics, Lecture Notes in Computer Science, Vol. 4286. Springer, Berlin, pp. 239-250.
[11] Charkhgard, H., Savelsbergh, M., Talebian, M., 2018. A linear programming based algorithm to solve a class of optimization problems with a multi‐linear objective function and affine constraints. Computers & Operations Research89, 17-30. · Zbl 1391.90406
[12] Coit, D.W., 2001. Cold‐standby redundancy optimization for nonrepairable systems. IIE Transactions33, 6, 471-478.
[13] Coit, D.W., Konak, A., 2006. Multiple weighted objectives heuristic for the redundancy allocation problem. IEEE Transactions on Reliability55, 3, 551-558.
[14] Dächert, K., Klamroth, K., 2014. A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems. Journal of Global Optimization61, 1-34.
[15] Dolan, E.D., Moré, J.J., 2002. Benchmarking optimization software with performance profiles. Mathematical Programming91, 2, 201-213. · Zbl 1049.90004
[16] Ehrgott, M., 2005. Multicriteria Optimization (second edn). Springer, New York. · Zbl 1132.90001
[17] Ehrgott, M., Gandibleux, X., 2007. Bound sets for biobjective combinatorial optimization problems. Computers & Operations Research34, 9, 2674-2694. · Zbl 1141.90509
[18] Eisenberg, E., Gale, D., 1959. Consensus of subjective probabilities: the pari‐mutuel method. The Annals of Mathematical Statistics30, 1, 165-168. · Zbl 0087.13805
[19] Eusébio, A., Figueira, J., Ehrgott, M., 2014. On finding representative non‐dominated points for bi‐objective integer network flow problems. Computers & Operations Research48, 1-10. · Zbl 1348.90154
[20] Feizabadi, M., Jahromi, A.E., 2017. A new model for reliability optimization of series‐parallel systems with non‐homogeneous components. Reliability Engineering & System Safety157, 101-112.
[21] Fischetti, M., Glover, F., Lodi, A., 2005. The feasibility pump. Mathematical Programming104, 1, 91-104. · Zbl 1077.90039
[22] Fischetti, M., Lodi, A., 2003. Local branching. Mathematical Programming98, 1, 23-47. · Zbl 1060.90056
[23] Fonseca, M., Figueira, J.R., Resende, M.G., 2010. Solving scalarized multi‐objective network flow problems using an interior point method. International Transactions in Operational Research17, 5, 607-636. · Zbl 1213.90074
[24] Gao, Y., Xu, C., Yang, Y., 2006. An outcome‐space finite algorithm for solving linear multiplicative programming. Applied Mathematics and Computation179, 2, 494-505. · Zbl 1103.65065
[25] Grötschel, M., Lovasz, L., Schrijver, A., 1988. Geometric Algorithms and Combinatorial Optimization. Springer, Berlin. · Zbl 0634.05001
[26] Haider, Z., Charkhgard, H., Kwon, C., 2018. A robust optimization approach for solving problems in conservation planning. Ecological Modelling368, 288-297.
[27] Hamming, R.W., 1950. Error detecting and error correcting codes. Bell System Technical Journal29, 2, 147-160. · Zbl 1402.94084
[28] Hooker, J., 2011. Logic‐Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Vol. 2. John Wiley & Sons, Hoboken, NJ.
[29] IBM ILOG CPLEX Optimization Studio, 2016. CPLEX Parameters Reference, Version 12 Release 8. Available at https://www.ibm.com/support/knowledgecenter/SSSA5P.
[30] Jain, K., Vazirani, V.V., 2007. Eisenberg-Gale markets: algorithms and structural properties. Proceedings of the Thirty‐Ninth Annual ACM Symposium on Theory of Computing. ACM, New York, NY, pp. 364-373. · Zbl 1232.91452
[31] Jorge, J.M., 2009. An algorithm for optimizing a linear function over an integer efficient set. European Journal of Operational Research195, 1, 98-103. · Zbl 1161.90443
[32] Karasakal, E., Köksalan, M., 2009. Generating a representative subset of the nondominated frontier in multiple criteria decision making. Operations Research57, 1, 187-199. · Zbl 1181.90150
[33] Kirlik, G., Sayın, S., 2014. A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems. European Journal of Operational Research232, 3, 479-488. · Zbl 1305.90368
[34] Lokman, B., Köksalan, M., 2013. Finding all nondominated points of multi‐objective integer programs. Journal of Global Optimization57, 2, 347-365. · Zbl 1315.90008
[35] Masin, M., Bukchin, Y., 2008. Diversity maximization approach for multiobjective optimization. Operations Research56, 2, 411-424. · Zbl 1167.90644
[36] Nash, J.F., 1950. The bargaining problem. Econometrica18, 155-162. · Zbl 1202.91122
[37] Nash, J.F., 1953. Two‐person cooperative games. Econometrica21, 128-140. · Zbl 0050.14102
[38] Nicholson, E., Possingham, H.P., 2006a. Objectives for multiple‐species conservation planning. Conservation Biology20, 3, 871-881.
[39] Nicholson, E., Possingham, H.P., 2006b. Objectives for multiple‐species conservation planning. Conservation Biology20, 3, 871-881.
[40] Özlen, M., Burton, B.A., MacRae, C.A.G., 2013. Multi‐objective integer programming: an improved recursive algorithm. Journal of Optimization Theory and Applications160, 470-482. · Zbl 1300.90044
[41] Özpeynirci, Ö., Köksalan, M., 2010. An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Management Science56, 12, 2302-2315. · Zbl 1232.90329
[42] Przybylski, A., Gandibleux, X., 2017. Multi‐objective branch and bound. European Journal of Operational Research260, 3, 856-872. · Zbl 1403.90615
[43] Ryoo, H.S., Sahinidis, N.V., 2003. Global optimization of multiplicative programs. Journal of Global Optimization26, 4, 387-418. · Zbl 1052.90091
[44] Saghand, P.G., Charkhgard, H., Kwon, C., 2019. A branch‐and‐bound algorithm for a class of mixed integer linear maximum multiplicative programs: a bi‐objective optimization approach. Computers & Operations Research101, 263-274. · Zbl 1458.90573
[45] Sayın, S., 2000. Optimizing over the efficient set using a top‐down search of faces. Operations Research48, 1, 65-72. · Zbl 1106.90376
[46] Sayın, S., 2003. A procedure to find discrete representations of the efficient set with specified coverage errors. Operations Research51, 3, 427-436. · Zbl 1163.90741
[47] Serrano, R., 2005. Fifty years of the Nash program 1953‐2003. Investigaciones Economicas29, 219-258.
[48] Shao, L., Ehrgott, M., 2014. An objective space cut and bound algorithm for convex multiplicative programmes. Journal of Global Optimization58, 4, 711-728. · Zbl 1298.90081
[49] Shao, L., Ehrgott, M., 2016. Primal and dual multi‐objective linear programming algorithms for linear multiplicative programmes. Optimization65, 2, 415-431. · Zbl 1370.90254
[50] Soylu, B., Yıldız, G.B., 2016. An exact algorithm for biobjective mixed integer linear programming problems. Computers & Operations Research72, 204-213. · Zbl 1349.90650
[51] Talbi, E.G., Basseur, M., Nebro, A.J., Alba, E., 2012. Multi‐objective optimization using metaheuristics: non‐standard algorithms. International Transactions in Operational Research19, 1-2, 283-305. · Zbl 1270.90067
[52] Vazirani, V.V., 2012a. The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. Journal of the ACM59, 7. · Zbl 1281.91095
[53] Vazirani, V.V., 2012b. Rational convex programs and efficient algorithms for 2‐player Nash and nonsymmetric bargaining games. SIAM Journal on Discrete Mathematics26, 3, 896-918. · Zbl 1258.68189
[54] Williams, P.H., Araújo, M.B., 2002. Apples, oranges, and probabilities: integrating multiple factors into biodiversity conservation with consistency. Environmental Modeling & Assessment7, 2, 139-151.
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.