{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T06:08:56Z","timestamp":1781071736392,"version":"3.54.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T00:00:00Z","timestamp":1690934400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T00:00:00Z","timestamp":1690934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007826","name":"Technische Universit\u00e4t Ilmenau","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007826","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In multi-objective mixed-integer convex optimization, multiple convex objective functions need to be optimized simultaneously while some of the variables are restricted to take integer values. In this paper, we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization problem into several multi-objective continuous convex optimization problems, which we refer to as patches. We then dynamically compute and improve coverages of the nondominated sets of those patches to finally combine them to obtain an enclosure of the nondominated set of the multi-objective mixed-integer convex optimization problem. Additionally, we introduce a mechanism to reduce the number of patches that need to be considered in total. Our new algorithm is the first of its kind and guaranteed to return an enclosure of prescribed quality within a finite number of iterations. For selected numerical test instances we compare our new criterion space based approach to other algorithms from the literature and show that much larger instances can be solved with our new algorithm.<\/jats:p>","DOI":"10.1007\/s00186-023-00828-x","type":"journal-article","created":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T15:05:33Z","timestamp":1690988733000},"page":"291-320","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems"],"prefix":"10.1007","volume":"100","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1938-6316","authenticated-orcid":false,"given":"Gabriele","family":"Eichfelder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2177-8466","authenticated-orcid":false,"given":"Leo","family":"Warnow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,8,2]]},"reference":[{"issue":"4","key":"828_CR1","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1287\/ijoc.2015.0646","volume":"27","author":"N Boland","year":"2015","unstructured":"Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective mixed integer programming: the triangle splitting method. INFORMS J Comput 27(4):597\u2013618","journal-title":"INFORMS J Comput"},{"issue":"2","key":"828_CR2","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.disopt.2006.10.011","volume":"5","author":"P Bonami","year":"2008","unstructured":"Bonami P, Biegler LT, Conn AR et al (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discret Optim 5(2):186\u2013204","journal-title":"Discret Optim"},{"issue":"8","key":"828_CR3","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.1080\/0305215X.2021.1939695","volume":"54","author":"RS Burachik","year":"2022","unstructured":"Burachik RS, Kaya CY, Rizvi MM (2022) Algorithms for generating Pareto fronts of multi-objective integer and mixed-integer programming problems. Eng Optim 54(8):1413\u20131425","journal-title":"Eng Optim"},{"issue":"2","key":"828_CR4","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.1007\/s10479-020-03910-3","volume":"319","author":"G Cabrera-Guerrero","year":"2022","unstructured":"Cabrera-Guerrero G, Ehrgott M, Mason AJ et al (2022) Bi-objective optimisation over a set of convex sub-problems. Ann Oper Res 319(2):1507\u20131532","journal-title":"Ann Oper Res"},{"key":"828_CR5","unstructured":"Currie J (2019) OPTI toolbox. https:\/\/github.com\/jonathancurrie\/OPTI. Accessed 23 Feb 2023"},{"issue":"4","key":"828_CR6","doi-asserted-by":"publisher","first-page":"3122","DOI":"10.1137\/19M1264709","volume":"30","author":"M De Santis","year":"2020","unstructured":"De Santis M, Eichfelder G, Niebling J et al (2020) Solving multiobjective mixed integer convex optimization problems. SIAM J Optim 30(4):3122\u20133145","journal-title":"SIAM J Optim"},{"key":"828_CR7","unstructured":"De Santis M, Eichfelder G, Niebling J, et\u00a0al (2021) MOMIX. https:\/\/github.com\/mariannadesantis\/MOMIX. Accessed 23 Feb 2023"},{"issue":"15","key":"828_CR8","doi-asserted-by":"publisher","first-page":"4321","DOI":"10.1080\/02331934.2021.1939699","volume":"71","author":"E Diessel","year":"2022","unstructured":"Diessel E (2022) An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems. Optimization 71(15):4321\u20134366","journal-title":"Optimization"},{"key":"828_CR9","volume-title":"Multicriteria optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M (2005) Multicriteria optimization. Springer, Berlin"},{"issue":"9","key":"828_CR10","doi-asserted-by":"publisher","first-page":"2674","DOI":"10.1016\/j.cor.2005.10.003","volume":"34","author":"M Ehrgott","year":"2007","unstructured":"Ehrgott M, Gandibleux X (2007) Bound sets for biobjective combinatorial optimization problems. Comput Oper Res 34(9):2674\u20132694","journal-title":"Comput Oper Res"},{"key":"828_CR11","doi-asserted-by":"crossref","unstructured":"Eichfelder G, Warnow L (2021a) An approximation algorithm for multi-objective optimization problems using a box-coverage. J Glob Optim 83:329\u2013357","DOI":"10.1007\/s10898-021-01109-9"},{"key":"828_CR12","unstructured":"Eichfelder G, Warnow L (2021b) On implementation details and numerical experiments for the HyPaD algorithm to solve multi-objective mixed-integer convex optimization problems. https:\/\/optimization-online.org\/2021\/08\/8538\/"},{"key":"828_CR13","unstructured":"Eichfelder G, Warnow L (2022) HyPaD. https:\/\/github.com\/LeoWarnow\/HyPaD. Accessed 23 Feb 2023"},{"key":"828_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10898-020-00984-y","volume":"80","author":"G Eichfelder","year":"2021","unstructured":"Eichfelder G, Kirst P, Meng L et al (2021) A general branch-and-bound framework for continuous global multiobjective optimization. J Glob Optim 80:195\u2013227","journal-title":"J Glob Optim"},{"key":"828_CR15","doi-asserted-by":"crossref","unstructured":"Eichfelder G, Stein O, Warnow L (2022) A deterministic solver for multiobjective mixed-integer convex and nonconvex optimization. https:\/\/optimization-online.org\/2022\/02\/8796\/","DOI":"10.1007\/s10957-023-02285-2"},{"key":"828_CR16","doi-asserted-by":"crossref","unstructured":"Eichfelder G, Gerlach T, Warnow L (2023) A test instance generator for multiobjective mixed-integer optimization. https:\/\/doi.org\/10.1007\/s00186-023-00826-z.","DOI":"10.1007\/s00186-023-00826-z"},{"issue":"1\u20133","key":"828_CR17","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01581153","volume":"66","author":"R Fletcher","year":"1994","unstructured":"Fletcher R, Leyffer S (1994) Solving mixed integer nonlinear programs by outer approximation. Math Program 66(1\u20133):327\u2013349","journal-title":"Math Program"},{"key":"828_CR18","volume-title":"Variational methods in partially ordered spaces","author":"A G\u00f6pfert","year":"2003","unstructured":"G\u00f6pfert A, Riahi H, Tammer C et al (2003) Variational methods in partially ordered spaces. Springer, Berlin"},{"key":"828_CR19","unstructured":"Gurobi Optimization LLC (2023) Gurobi. https:\/\/www.gurobi.com\/. Accessed 23 Feb 2023"},{"issue":"5\u20136","key":"828_CR20","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1002\/mcda.1780","volume":"29","author":"P Halffmann","year":"2022","unstructured":"Halffmann P, Sch\u00e4fer LE, D\u00e4chert K et al (2022) Exact algorithms for multiobjective linear optimization problems with integer variables: a state of the art survey. J Multi-Criteria Decis Anal 29(5\u20136):341\u2013363","journal-title":"J Multi-Criteria Decis Anal"},{"key":"828_CR21","unstructured":"IBM (2023) CPLEX optimizer. https:\/\/www.ibm.com\/analytics\/cplex-optimizer. Accessed 23 Feb 2023"},{"issue":"3","key":"828_CR22","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1016\/j.ejor.2015.03.031","volume":"245","author":"K Klamroth","year":"2015","unstructured":"Klamroth K, Lacour R, Vanderpooten D (2015) On the representation of the search region in multi-objective optimization. Eur J Oper Res 245(3):767\u2013778","journal-title":"Eur J Oper Res"},{"issue":"12","key":"828_CR23","doi-asserted-by":"publisher","first-page":"2302","DOI":"10.1287\/mnsc.1100.1248","volume":"56","author":"\u00d6 \u00d6zpeynirci","year":"2010","unstructured":"\u00d6zpeynirci \u00d6, K\u00f6ksalan M (2010) An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Manag Sci 56(12):2302\u20132315","journal-title":"Manag Sci"},{"issue":"4","key":"828_CR24","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF00934564","volume":"42","author":"A Pascoletti","year":"1984","unstructured":"Pascoletti A, Serafini P (1984) Scalarizing vector optimization problems. J Optim Theory Appl 42(4):499\u2013524","journal-title":"J Optim Theory Appl"},{"issue":"1","key":"828_CR25","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1287\/ijoc.2019.0887","volume":"32","author":"T Perini","year":"2020","unstructured":"Perini T, Boland N, Pecin D et al (2020) A criterion space method for biobjective mixed integer programming: the boxed line method. INFORMS J Comput 32(1):16\u201339","journal-title":"INFORMS J Comput"},{"key":"828_CR26","unstructured":"Przybylski A, Klamroth K, Lacour R (2019) A simple and efficient dichotomic search algorithm for multi-objective mixed integer linear programs. arXiv:1911.08937"},{"issue":"1","key":"828_CR27","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s11081-018-9399-0","volume":"20","author":"SAB Rasmi","year":"2019","unstructured":"Rasmi SAB, T\u00fcrkay M (2019) GoNDEF: an exact method to generate all non-dominated points of multi-objective mixed-integer linear programs. Optim Eng 20(1):89\u2013117","journal-title":"Optim Eng"},{"issue":"1","key":"828_CR28","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1007\/s10479-015-1806-8","volume":"229","author":"R Roozbahani","year":"2015","unstructured":"Roozbahani R, Abbasi B, Schreider S (2015) Optimal allocation of water to competing stakeholders in a shared watershed. Ann Oper Res 229(1):657\u2013676","journal-title":"Ann Oper Res"},{"key":"828_CR29","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-94-017-1247-7_7","volume-title":"Developments in reliable computing","author":"S Rump","year":"1999","unstructured":"Rump S (1999) INTLAB\u2014INTerval LABoratory. In: Csendes T (ed) Developments in reliable computing. Kluwer Academic Publishers, Dordrecht, pp 77\u2013104"},{"issue":"3","key":"828_CR30","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s10957-005-5494-4","volume":"126","author":"S Ruzika","year":"2005","unstructured":"Ruzika S, Wiecek MM (2005) Approximation methods in multiobjective programming. J Optim Theory Appl 126(3):473\u2013501","journal-title":"J Optim Theory Appl"},{"issue":"4","key":"828_CR31","doi-asserted-by":"publisher","first-page":"1214","DOI":"10.1080\/00207543.2018.1504172","volume":"57","author":"SK Singh","year":"2018","unstructured":"Singh SK, Goh M (2018) Multi-objective mixed integer programming and an application in a pharmaceutical supply chain. Int J Prod Res 57(4):1214\u20131237","journal-title":"Int J Prod Res"},{"key":"828_CR32","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.cor.2016.03.001","volume":"72","author":"B Soylu","year":"2016","unstructured":"Soylu B, Y\u0131ld\u0131z GB (2016) An exact algorithm for biobjective mixed integer linear programming problems. Comput Oper Res 72:204\u2013213","journal-title":"Comput Oper Res"},{"issue":"1","key":"828_CR33","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2005","unstructured":"W\u00e4chter A, Biegler LT (2005) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math Program 106(1):25\u201357","journal-title":"Math Program"},{"issue":"2","key":"828_CR34","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10898-009-9465-4","volume":"47","author":"P Xidonas","year":"2009","unstructured":"Xidonas P, Mavrotas G, Psarras J (2009) Equity portfolio construction and selection using multiobjective mathematical programming. J Glob Optim 47(2):185\u2013209","journal-title":"J Glob Optim"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00828-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-023-00828-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00828-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T09:05:10Z","timestamp":1725267910000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-023-00828-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,2]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["828"],"URL":"https:\/\/doi.org\/10.1007\/s00186-023-00828-x","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,2]]},"assertion":[{"value":"27 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}