{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T04:38:12Z","timestamp":1777351092520,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T00:00:00Z","timestamp":1710979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T00:00:00Z","timestamp":1710979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hochschule f\u00fcr Technik und Wirtschaft Dresden (HTW)"}],"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 the last years a multitude of algorithms have been proposed to solve multiobjective integer programming problems. However, only few authors offer open-source implementations. On the other hand, new methods are typically compared to code that is publicly available, even if this code is known to be outperformed. In this paper, we aim to overcome this problem by proposing a new state-of-the-art algorithm with an open-source implementation in . The underlying method falls into the class of objective space methods, i.e., it decomposes the overall problem into a series of scalarized subproblems that can be solved with efficient single-objective IP-solvers. It keeps the number of required subproblems small by avoiding redundancies, and it can be combined with different scalarizations that all lead to comparably simple subproblems. Our algorithm bases on previous results but combines them in a new way. Numerical experiments with up to ten objectives validate that the method is efficient and that it scales well to higher dimensional problems.<\/jats:p>","DOI":"10.1007\/s00186-023-00841-0","type":"journal-article","created":{"date-parts":[[2024,3,21]],"date-time":"2024-03-21T15:01:56Z","timestamp":1711033316000},"page":"351-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A simple, efficient and versatile objective space algorithm for multiobjective integer programming"],"prefix":"10.1007","volume":"100","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6458-6480","authenticated-orcid":false,"given":"Kerstin","family":"D\u00e4chert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tino","family":"Fleuren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathrin","family":"Klamroth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,21]]},"reference":[{"key":"841_CR1","doi-asserted-by":"crossref","unstructured":"Aneja YP, Nair KPK (1979) Bicriteria transportation problem. Mangement Science 25:73\u201378","DOI":"10.1287\/mnsc.25.1.73"},{"key":"841_CR2","doi-asserted-by":"crossref","unstructured":"Bekta\u015f T (2018) Disjunctive programming for multiobjective discrete optimisation. INFORMS J Comput 30(4):625\u2013633","DOI":"10.1287\/ijoc.2017.0804"},{"key":"841_CR3","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/PL00009366","volume":"19","author":"JD Boissonnat","year":"1998","unstructured":"Boissonnat JD, Sharir M, Tagansky B et al (1998) Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput Geometry 19:485\u2013519","journal-title":"Discrete Comput Geometry"},{"key":"841_CR4","doi-asserted-by":"crossref","unstructured":"Boland N, Charkhgard H, Savelsbergh M (2016) The L-shape search method for triobjective integer programming. Math Program Comput 8:217\u2013251","DOI":"10.1007\/s12532-015-0093-3"},{"key":"841_CR5","doi-asserted-by":"crossref","unstructured":"Boland N, Charkhgard H, Savelsbergh M (2017a) A new method for optimizing a linear function over the efficient set of a multiobjective integer program. Eur J Oper Res 260(3):904\u2013919","DOI":"10.1016\/j.ejor.2016.02.037"},{"key":"841_CR6","doi-asserted-by":"crossref","unstructured":"Boland N, Charkhgard H, Savelsbergh M (2017b) The quadrant shrinking method: a simple and efficient algorithm for solving tri-objective integer programs. Eur J Oper Res 260(3):873\u2013885","DOI":"10.1016\/j.ejor.2016.03.035"},{"key":"841_CR7","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/0377-2217(86)90093-7","volume":"25","author":"L Chalmet","year":"1986","unstructured":"Chalmet L, Lemonidis L, Elzinga D (1986) An algorithm for the bi-criterion integer programming problem. Eur J Oper Res 25:292\u2013300","journal-title":"Eur J Oper Res"},{"key":"841_CR8","doi-asserted-by":"crossref","unstructured":"D\u00e4chert K, Klamroth K (2015) A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems. J Global Optim 61(4):643\u2013676","DOI":"10.1007\/s10898-014-0205-z"},{"key":"841_CR9","doi-asserted-by":"publisher","first-page":"2929","DOI":"10.1016\/j.cor.2012.02.021","volume":"39","author":"K D\u00e4chert","year":"2012","unstructured":"D\u00e4chert K, Gorski J, Klamroth K (2012) An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems. Comput Oper Res 39:2929\u20132943","journal-title":"Comput Oper Res"},{"issue":"3","key":"841_CR10","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.ejor.2016.05.029","volume":"260","author":"K D\u00e4chert","year":"2017","unstructured":"D\u00e4chert K, Klamroth K, Lacour R et al (2017) Efficient computation of the search region in multi-objective optimization. Eur J Oper Res 260(3):841\u2013855","journal-title":"Eur J Oper Res"},{"key":"841_CR11","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.ejor.2008.12.034","volume":"200","author":"C Dhaenens","year":"2010","unstructured":"Dhaenens C, Lemesre J, Talbi EG (2010) K-PPM: a new exact method to solve multi-objective combinatorial optimization problems. Eur J Oper Res 200:45\u201353","journal-title":"Eur J Oper Res"},{"key":"841_CR12","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1016\/j.ejor.2021.04.005","volume":"296","author":"I Do\u011fan","year":"2022","unstructured":"Do\u011fan I, Lokman B, K\u00f6ksalan M (2022) Representing the nondominated set in multi-objective mixed-integer programs. Eur J Oper Res 296:804\u2013818","journal-title":"Eur J Oper Res"},{"key":"841_CR13","volume-title":"Multicriteria optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott M (2005) Multicriteria optimization. Springer, Berlin"},{"key":"841_CR14","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10479-006-0074-z","volume":"147","author":"M Ehrgott","year":"2006","unstructured":"Ehrgott M (2006) A discussion of scalarization techniques for multiple objective integer programming. Ann Oper Res 147:343\u2013360","journal-title":"Ann Oper Res"},{"key":"841_CR15","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10957-008-9394-2","volume":"138","author":"M Ehrgott","year":"2008","unstructured":"Ehrgott M, Ruzika S (2008) Improved $$\\varepsilon $$-constraint method for multiobjective programming. J Optim Theory Appl 138:375\u2013396","journal-title":"J Optim Theory Appl"},{"key":"841_CR16","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0377-2217(02)00595-7","volume":"151","author":"M Ehrgott","year":"2003","unstructured":"Ehrgott M, Tenfelde-Podehl D (2003) Computation of ideal and Nadir values and implications for their use in MCDM methods. Eur J Oper Res 151:119\u2013139","journal-title":"Eur J Oper Res"},{"key":"841_CR17","doi-asserted-by":"crossref","unstructured":"Figueira et al. (2017) Easy to say they\u2019re hard, but hard to see they\u2019re easy - toward a categorization of tractable multiobjective combinatorial optimization problems. J Multi-Criteria Decis Anal 24:82\u201398","DOI":"10.1002\/mcda.1574"},{"key":"841_CR18","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/j.ejor.2018.05.036","volume":"271","author":"T Holzmann","year":"2018","unstructured":"Holzmann T, Smith J (2018) Solving discrete multi-objective optimization problems using modified augmented weighted Tchebychev scalarizations. Eur J Oper Res 271:436\u2013449","journal-title":"Eur J Oper Res"},{"key":"841_CR19","doi-asserted-by":"publisher","first-page":"1172","DOI":"10.1137\/17M1153066","volume":"34","author":"M Joswig","year":"2020","unstructured":"Joswig M, Loho G (2020) Monomial tropical cones for multicriteria optimization. SIAM J Discrete Math 34:1172\u20131191","journal-title":"SIAM J Discrete Math"},{"key":"841_CR20","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1137\/070684483","volume":"38","author":"H Kaplan","year":"2008","unstructured":"Kaplan H, Rubin N, Sharir M et al (2008) Efficient colored orthogonal range counting. SIAM J Comput 38:982\u20131011","journal-title":"SIAM J Comput"},{"key":"841_CR21","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.ejor.2013.08.001","volume":"232","author":"G Kirlik","year":"2014","unstructured":"Kirlik G, Say\u0131n S (2014) A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems. Eur J Oper Res 232:479\u2013488","journal-title":"Eur J Oper Res"},{"issue":"3","key":"841_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"},{"key":"841_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/0377-2217(82)90182-5","volume":"9","author":"D Klein","year":"1982","unstructured":"Klein D, Hannan E (1982) An algorithm for the multiple objective integer linear programming problem. Eur J Oper Res 9:378\u2013385","journal-title":"Eur J Oper Res"},{"key":"841_CR24","unstructured":"Laumanns M, Thiele L, Zitzler E (2005) An adaptive scheme to generate the pareto front based on the epsilon-constraint method. In: Branke J, Deb K, Miettinen K, et\u00a0al. (eds) Practical approaches to multi-objective optimization. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany, Dagstuhl, Germany, no. 04461 in Dagstuhl Seminar Proceedings, http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2005\/246"},{"key":"841_CR25","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1016\/j.ejor.2004.08.029","volume":"169","author":"M Laumanns","year":"2006","unstructured":"Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur J Oper Res 169:932\u2013942","journal-title":"Eur J Oper Res"},{"key":"841_CR26","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10898-012-9955-7","volume":"57","author":"B Lokman","year":"2013","unstructured":"Lokman B, K\u00f6ksalan M (2013) Finding all nondominated points of multi-objective integer programs. J Global Optim 57:347\u2013365","journal-title":"J Global Optim"},{"key":"841_CR27","volume-title":"Nonlinear multiobjective optimization","author":"K Miettinen","year":"1999","unstructured":"Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer Academic Publishers, Boston"},{"key":"841_CR28","volume-title":"Integer and combinatorial optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization. Wiley"},{"key":"841_CR29","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ejor.2008.10.023","volume":"199","author":"M \u00d6zlen","year":"2009","unstructured":"\u00d6zlen M, Azizo\u011flu M (2009) Multi-objective integer programming: a general approach for generating all non-dominated solutions. Eur J Oper Res 199:25\u201335","journal-title":"Eur J Oper Res"},{"issue":"2","key":"841_CR30","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1007\/s10957-013-0364-y","volume":"160","author":"M \u00d6zlen","year":"2014","unstructured":"\u00d6zlen M, Burton BA, MacRae CAG (2014) Multi-objective integer programming: an improved recursive algorithm. J Optim Theory Appl 160(2):470\u2013482","journal-title":"J Optim Theory Appl"},{"key":"841_CR31","doi-asserted-by":"crossref","unstructured":"Pettersson W, Ozlen M (2019) Multi-objective integer programming: Synergistic parallel approaches. INFORMS J Comput","DOI":"10.1287\/ijoc.2018.0875"},{"key":"841_CR32","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.disopt.2010.03.005","volume":"7","author":"A Przybylski","year":"2010","unstructured":"Przybylski A, Gandibleux X, Ehrgott M (2010) A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optim 7:149\u2013165","journal-title":"Discrete Optim"},{"key":"841_CR33","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10479-006-0058-z","volume":"147","author":"T Ralphs","year":"2006","unstructured":"Ralphs T, Saltzman M, Wiecek MM (2006) An improved algorithm for solving biobjective integer programs. Ann Oper Res 147:43\u201370","journal-title":"Ann Oper Res"},{"key":"841_CR34","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/S0377-2217(03)00255-8","volume":"158","author":"J Sylva","year":"2004","unstructured":"Sylva J, Crema A (2004) A method for finding the set of non-dominated vectors for multiple objective integer linear programs. Eur J Oper Res 158:46\u201355","journal-title":"Eur J Oper Res"},{"issue":"3","key":"841_CR35","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1051\/ro:2008018","volume":"42","author":"J Sylva","year":"2008","unstructured":"Sylva J, Crema A (2008) Enumerating the set of non-dominated vectors in multiple objective integer linear programming. RAIRO-Oper Res 42(3):371\u2013387","journal-title":"RAIRO-Oper Res"},{"key":"841_CR36","unstructured":"Tamby S (2018) Approches g\u00e9n\u00e9riques pour la r\u00e9solution de probl\u00e8mes d\u2019optimisation discr\u00e8te multiobjectif. PhD thesis, Universit\u00e9 Paris-Dauphine, in French"},{"key":"841_CR37","doi-asserted-by":"crossref","unstructured":"Tamby S, Vanderpooten D (2020) Enumeration of the nondominated set of multiobjective discrete optimization problems. INFORMS J Comput","DOI":"10.1287\/ijoc.2020.0953"},{"key":"841_CR38","unstructured":"Tenfelde-Podehl D (2003) A recursive algorithm for multiobjective combinatorial optimization problems with Q criteria. Institut f\u00fcr Mathematik, Technische Universit\u00e4t Graz, Tech. rep"},{"key":"841_CR39","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10898-019-00778-x","volume":"75","author":"O Turgut","year":"2019","unstructured":"Turgut O, Dalkiran E, Murat A (2019) An exact parallel objective space decomposition algorithm for solving multiobjective integer programming problems. J Global Optim 75:35\u201362","journal-title":"J Global Optim"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00841-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-023-00841-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-023-00841-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T09:05:24Z","timestamp":1725267924000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-023-00841-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,21]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["841"],"URL":"https:\/\/doi.org\/10.1007\/s00186-023-00841-0","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,21]]},"assertion":[{"value":"26 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We assure that there is no conflict of interest concerning the publication of this manuscript in MMOR. Kathrin Klamroth declares financial support by the Deutsche Forschungsgemeinschaft, project number\u00a0KL\u00a01076\/11-1. The other two authors have not received specific funding. All sources of data that have been used for this work are properly declared and referenced.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}