Adaptive piecewise linear relaxations for enclosure computations for nonconvex multiobjective mixed-integer quadratically constrained programs. (English) Zbl 1522.65095
Summary: In this paper, a new method for computing an enclosure of the nondominated set of multiobjective mixed-integer quadratically constrained programs without any convexity requirements is presented. In fact, our criterion space method makes use of piecewise linear relaxations in order to bypass the nonconvexity of the original problem. The method chooses adaptively which level of relaxation is needed in which parts of the image space. Furthermore, it is guaranteed that after finitely many iterations, an enclosure of the nondominated set of prescribed quality is returned. We demonstrate the advantages of this approach by applying it to multiobjective energy supply network problems.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C11 | Mixed integer programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C29 | Multi-objective and goal programming |
| 90C35 | Programming involving graphs or networks |
Keywords:
mixed-integer nonlinear programming; multiobjective optimization; box enclosure; adaptive piecewise linear relaxation; energy supply networksReferences:
| [1] | Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Facets of Combinatorial Optimization, pp. 449-481. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38189-8_18 · Zbl 1317.90206 |
| [2] | Adjiman, CS; Dallwig, S.; Floudas, CA; Neumaier, A., A global optimization method, \( \alpha\) BB, for general twice-differentiable constrained NLPs—I. Theoretical advances, Comput. Chem. Eng., 22, 9, 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1 |
| [3] | Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \( \alpha \text{BB} \): a global optimization method for general constrained nonconvex problems, vol. 7, pp. 337-363 (1995). doi:10.1007/BF01099647. State of the art in global optimization: computational methods and applications (Princeton, NJ, 1995). doi:10.1007/BF01099647 · Zbl 0846.90087 |
| [4] | Banholzer, S.: Rom-Based Multiobjective Optimization with PDE Constraints. Ph.D. thesis, Universität Konstanz, Konstanz (2021) |
| [5] | Banholzer, S., Gebken, B., Dellnitz, M., Peitz, S., Volkwein, S.: ROM-based multiobjective optimization of elliptic PDEs via numerical continuation. In: Non-smooth and Complementarity-based Distributed Parameter Systems—Simulation and Hierarchical Optimization. Int. Ser. Numer. Math., vol. 172, pp. 43-76. Birkhäuser/Springer, Cham (2022). doi:10.1007/978-3-030-79393-7_3 · Zbl 1507.90161 |
| [6] | Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172 · doi:10.1017/S0962492913000032 |
| [7] | Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S.J., Matter, F., Mühmer, E., Müller, B., Pfetsch, M.E., Rehfeldt, D., Schlein, S., Schlösser, F., Serrano, F., Shinano, Y., Sofranac, B., Turner, M., Vigerske, S., Wegscheider, F., Wellner, P., Weninger, D., Witzig, J.: The SCIP Optimization Suite 8.0. ZIB-Report 21-41, Zuse Institute Berlin (2021). http://nbn-resolving.de/urn:nbn:de:0297-zib-85309 |
| [8] | Borraz-Sánchez, C.; Bent, R.; Backhaus, S.; Hijazi, H.; Van Hentenryck, P., Convex relaxations for gas expansion planning, INFORMS J. Comput., 28, 4, 645-656 (2016) · Zbl 1355.90063 · doi:10.1287/ijoc.2016.0697 |
| [9] | Boukouvala, F.; Misener, R.; Floudas, CA, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Eur. J. Oper. Res., 252, 3, 701-727 (2016) · Zbl 1346.90677 · doi:10.1016/j.ejor.2015.12.018 |
| [10] | Burachik, RS; Kaya, CY; Rizvi, MM, Algorithms for generating pareto fronts of multi-objective integer and mixed-integer programming problems, Eng. Optim. (2021) · Zbl 1523.90292 · doi:10.1080/0305215X.2021.1939695 |
| [11] | Burlacu, R.: Adaptive mixed-integer refinements for solving nonlinear problems with discrete decisions. Ph.D. thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg (2019) |
| [12] | Burlacu, R., On refinement strategies for solving MINLPs by piecewise linear relaxations: a general red refinement, Optim. Lett. (2021) · Zbl 1487.90484 · doi:10.1007/s11590-021-01740-1 |
| [13] | Burlacu, R.; Geißler, B.; Schewe, L., Solving mixed-integer nonlinear programmes using adaptively refined mixed-integer linear programmes, Optim. Methods Softw., 35, 1, 37-64 (2020) · Zbl 1432.90089 · doi:10.1080/10556788.2018.1556661 |
| [14] | Cplex, II, V12. 1: user’s manual for CPLEX, Int. Bus. Mach. Corp., 46, 53, 157 (2009) |
| [15] | Dächert, K.; Klamroth, K.; Lacour, R.; Vanderpooten, D., Efficient computation of the search region in multi-objective optimization, Eur. J. Oper. Res., 260, 3, 841-855 (2017) · Zbl 1403.90602 · doi:10.1016/j.ejor.2016.05.029 |
| [16] | De Santis, M.; Eichfelder, G.; Niebling, J.; Rocktäschel, S., Solving multiobjective mixed integer convex optimization problems, SIAM J. Optim., 30, 4, 3122-3145 (2020) · Zbl 1453.90139 · doi:10.1137/19M1264709 |
| [17] | Diessel, E., An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems, Optimization, 0, 1-46 (2021) · Zbl 1508.90089 · doi:10.1080/02331934.2021.1939699 |
| [18] | Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064 |
| [19] | Eggen, C., Huynh, T.-V., Link, M., Stephan, P., Volkwein, S.: An MINLP model for designing decentralized energy supply networks. Technical report. arXiv:2212.06527 (2022) |
| [20] | Ehrgott, M., Multicriteria Optimization, 323 (2005), Berlin: Springer, Berlin · Zbl 1132.90001 |
| [21] | Ehrgott, M.; Gandibleux, X., Bound sets for biobjective combinatorial optimization problems, Comput. Oper. Res., 34, 9, 2674-2694 (2007) · Zbl 1141.90509 · doi:10.1016/j.cor.2005.10.003 |
| [22] | Eichfelder, G., Twenty years of continuous multiobjective optimization in the twenty-first century, EURO J. Comput. Optim., 9 (2021) · Zbl 1530.90091 · doi:10.1016/j.ejco.2021.100014 |
| [23] | Eichfelder, G., Warnow, L.: An approximation algorithm for multi-objective optimization problems using a box-coverage. J. Global Optim. (2021) · Zbl 1489.90173 |
| [24] | Eichfelder, G., Warnow, L.: A hybrid patch decomposition approach to compute an enclosure for multiobjective mixed-integer convex optimization problems (2021) |
| [25] | Eichfelder, G., Stein, O., Warnow, L.: A deterministic solver for multiobjective mixed-integer convex and nonconvex optimization (2022) |
| [26] | Eichfelder, G.; Kirst, P.; Meng, L.; Stein, O., A general branch-and-bound framework for continuous global multiobjective optimization, J. Global Optim., 80, 1, 195-227 (2021) · Zbl 1470.90114 · doi:10.1007/s10898-020-00984-y |
| [27] | Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 3, 327-349 (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153 |
| [28] | Geißler, B., Martin, A., Morsi, A., Schewe, L.: Using piecewise linear functions for solving MINLPs. In: Mixed Integer Nonlinear Programming. IMA Vol. Math. Appl., vol. 154, pp. 287-314. Springer, New York (2012) · Zbl 1242.90132 |
| [29] | Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022). https://www.gurobi.com |
| [30] | Iapichino, L., Trenz, S., Volkwein, S.: Reduced-order multiobjective optimal control of semilinear parabolic problems. In: Numerical Mathematics and Advanced Applications—ENUMATH 2015. Lect. Notes Comput. Sci. Eng., vol. 112, pp. 389-397. Springer, Cham (2016) · Zbl 1352.65166 |
| [31] | Kim, IY; de Weck, O., Adaptive weighted sum method for bi-objective optimization: Pareto front generation, Struct. Multidiscip. Optim., 29, 149-158 (2005) · doi:10.1007/s00158-004-0465-1 |
| [32] | Kim, IY; de Weck, O., Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation, Struct. Multidiscip. Optim., 31, 2, 105-116 (2006) · Zbl 1245.90117 · doi:10.1007/s00158-005-0557-6 |
| [33] | Kirlik, G.; Sayın, S., Bilevel programming for generating discrete representations in multiobjective optimization, Math. Program., 169, 2, 585-604 (2018) · Zbl 1391.90555 · doi:10.1007/s10107-017-1149-0 |
| [34] | Klamroth, K.; Lacour, R.; Vanderpooten, D., On the representation of the search region in multi-objective optimization, Eur. J. Oper. Res., 245, 3, 767-778 (2015) · Zbl 1346.90739 · doi:10.1016/j.ejor.2015.03.031 |
| [35] | Kronqvist, J.; Lundell, A.; Westerlund, T., The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 64, 2, 249-272 (2016) · Zbl 1339.90247 · doi:10.1007/s10898-015-0322-3 |
| [36] | Lee, J., Leyffer, S. (eds.): Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol. 154, p. 690. Springer, New York (2012). doi:10.1007/978-1-4614-1927-3. Selected papers based on the IMA Hot Topics Workshop “Mixed-Integer Nonlinear Optimization: Algorithmic Advances and Applications” held in Minneapolis, MN, November 17-21, 2008. doi:10.1007/978-1-4614-1927-3 |
| [37] | Liberti, L., Reformulation and convex relaxation techniques for global optimization, Q. J. Belg. Fr. Ital. Oper. Res. Soc., 2, 255-258 (2004) · Zbl 1136.90442 · doi:10.1007/s10288-004-0038-6 |
| [38] | Lu, J.: Mixed-Integer Nonlinear Modeling and Optimization of Designing Decentralized Energy Supply Networks. Ph.D. thesis, Universität Konstanz, Konstanz (2023) |
| [39] | Lundell, A.; Kronqvist, J., Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT, J. Global Optim., 82, 4, 863-896 (2022) · Zbl 1490.90200 · doi:10.1007/s10898-021-01006-1 |
| [40] | Lundell, A.; Skjäl, A.; Westerlund, T., A reformulation framework for global optimization, J. Global Optim., 57, 1, 115-141 (2013) · Zbl 1277.90102 · doi:10.1007/s10898-012-9877-4 |
| [41] | Maher, S., Miltenberger, M., Pedroso, J.P., Rehfeldt, D., Schwarz, R., Serrano, F.: PySCIPOpt: mathematical programming in python with the SCIP optimization suite. In: Mathematical Software—ICMS 2016, pp. 301-307. Springer, Cham (2016). doi:10.1007/978-3-319-42432-3_37 · Zbl 1434.90005 |
| [42] | McCormick, GP, Computability of global solutions to factorable nonconvex programs. I. Convex underestimating problems, Math. Program., 10, 2, 147-175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [43] | Misener, R.; Floudas, CA, Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Math. Program., 136, 1, 155-182 (2012) · Zbl 1257.90079 · doi:10.1007/s10107-012-0555-6 |
| [44] | Morsi, A., Geißler, B., Martin, A.: Mixed integer optimization of water supply networks. In: Mathematical Optimization of Water Networks. Internat. Ser. Numer. Math., vol. 162, pp. 35-54. Birkhäuser/Springer Basel AG, Basel (2012). doi:10.1007/978-3-0348-0436-3_3 · Zbl 1259.90076 |
| [45] | Nagarajan, H.; Lu, M.; Wang, S.; Bent, R.; Sundar, K., An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs, J. Global Optim., 74, 4, 639-675 (2019) · Zbl 1429.90056 · doi:10.1007/s10898-018-00734-1 |
| [46] | Pascoletti, A.; Serafini, P., Scalarizing vector optimization problems, J. Optim. Theory Appl., 42, 4, 499-524 (1984) · Zbl 0505.90072 · doi:10.1007/BF00934564 |
| [47] | Perini, T.; Boland, N.; Pecin, D.; Savelsbergh, M., A criterion space method for biobjective mixed integer programming: the boxed line method, INFORMS J. Comput., 32, 1, 16-39 (2020) · Zbl 1528.90252 · doi:10.1287/ijoc.2019.0887 |
| [48] | Ryu, N.; Min, S., Multiobjective optimization with an adaptive weight determination scheme using the concept of hyperplane, Int. J. Numer. Methods Eng., 118, 6, 303-319 (2019) · Zbl 07865219 · doi:10.1002/nme.6013 |
| [49] | Sayın, S., Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming, Math. Program., 87, 3, 543-560 (2000) · Zbl 0970.90090 · doi:10.1007/s101070050128 |
| [50] | Skjäl, A.: On the use of convex under estimators in global optimization. Ph.D. thesis, Abo Akademi University (2014) |
| [51] | Stidsen, T.; Andersen, KA, A hybrid approach for biobjective optimization, Discrete Optim., 28, 89-114 (2018) · Zbl 1506.90241 · doi:10.1016/j.disopt.2018.02.001 |
| [52] | Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-integer Nonlinear Programming. Nonconvex Optimization and its Applications, vol. 65, p. 475. Kluwer Academic Publishers, Dordrecht (2002). doi:10.1007/978-1-4757-3532-1. Theory, algorithms, software, and applications · Zbl 1031.90022 |
| [53] | Vielma, JP; Ahmed, S.; Nemhauser, G., Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions, Oper. Res., 58, 2, 303-315 (2010) · Zbl 1226.90046 · doi:10.1287/opre.1090.0721 |
| [54] | Westerlund, T., Pettersson, F.: An extended cutting plane method for solving convex MINLP problems. Comput. Chem. Eng. 19, 131-136 (1995). doi:10.1016/0098-1354(95)87027-X. European Symposium on Computer Aided Process Engineering 3-5 |
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.
