{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:14:54Z","timestamp":1760346894543,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["DFG RU 1524\/4-1","DFG RU 1524\/2-2"],"award-info":[{"award-number":["DFG RU 1524\/4-1","DFG RU 1524\/2-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Agence nationale de la recherche","award":["ANR\/DFG-14-CE35-0034-01"],"award-info":[{"award-number":["ANR\/DFG-14-CE35-0034-01"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article is dedicated to the weight set decomposition of a multiobjective (mixed-)integer linear problem with three objectives. We propose an algorithm that returns a decomposition of the parameter set of the weighted sum scalarization by solving biobjective subproblems via <jats:italic>Dichotomic Search<\/jats:italic> which corresponds to a line exploration in the weight set. Additionally, we present theoretical results regarding the boundary of the weight set components that direct the line exploration. The resulting algorithm runs in output polynomial time, i.e. its running time is polynomial in the encoding length of both the input and output. Also, the proposed approach can be used for each weight set component individually and is able to give intermediate results, which can be seen as an \u201capproximation\u201d of the weight set component. We compare the running time of our method with the one of an existing algorithm and conduct a computational study that shows the competitiveness of our algorithm. Further, we give a state-of-the-art survey of algorithms in the literature.<\/jats:p>","DOI":"10.1007\/s10898-020-00898-9","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T06:02:40Z","timestamp":1583906560000},"page":"715-742","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An inner approximation method to compute the weight set decomposition of a triobjective mixed-integer problem"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3462-4941","authenticated-orcid":false,"given":"Pascal","family":"Halffmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Dietz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Przybylski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"issue":"1","key":"898_CR1","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.ejor.2015.06.072","volume":"248","author":"MJ Alves","year":"2016","unstructured":"Alves, M.J., Costa, J.P.: Graphical exploration of the weight space in three-objective mixed integer linear programs. Eur. J. Oper. Res. 248(1), 72\u201383 (2016). https:\/\/doi.org\/10.1016\/j.ejor.2015.06.072","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"898_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/mnsc.25.1.73","volume":"25","author":"YP Aneja","year":"1979","unstructured":"Aneja, Y.P., Nair, K.P.: Bicriteria transportation problem. Manag. Sci. 25(1), 73\u201378 (1979). https:\/\/doi.org\/10.1287\/mnsc.25.1.73","journal-title":"Manag. Sci."},{"key":"898_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"1\u20132","key":"898_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/mcda.1603.Mcda.1603","volume":"24","author":"F B\u00f6kler","year":"2017","unstructured":"B\u00f6kler, F., Ehrgott, M., Morris, C., Mutzel, P.: Output-sensitive complexity of multiobjective combinatorial optimization. J. Multi-Criteria Decision Anal. 24(1\u20132), 25\u201336 (2017). https:\/\/doi.org\/10.1002\/mcda.1603.Mcda.1603","journal-title":"J. Multi-Criteria Decision Anal."},{"key":"898_CR5","doi-asserted-by":"publisher","unstructured":"B\u00f6kler, F., Mutzel, P.: Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In: N.\u00a0Bansal, I.\u00a0Finocchi (eds.) Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp. 288\u2013299. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_25","DOI":"10.1007\/978-3-662-48350-3_25"},{"issue":"4","key":"898_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16(4), 361\u2013368 (1996). https:\/\/doi.org\/10.1007\/BF02712873","journal-title":"Discrete Comput. Geom."},{"key":"898_CR7","series-title":"Dover Books on Computer Science","volume-title":"Multiobjective Programming and Planning","author":"JL Cohon","year":"2004","unstructured":"Cohon, J.L.: Multiobjective Programming and Planning. Dover Books on Computer Science. Dover, Mineola (2004)"},{"key":"898_CR8","volume-title":"Multicriteria Optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)"},{"issue":"4","key":"898_CR9","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/s10898-011-9709-y","volume":"52","author":"M Ehrgott","year":"2012","unstructured":"Ehrgott, M., L\u00f6hne, A., Shao, L.: A dual variant of benson\u2019s \u201couter approximation algorithm\u201d for multiple objective linear programming. J. Global Optim. 52(4), 757\u2013778 (2012). https:\/\/doi.org\/10.1007\/s10898-011-9709-y","journal-title":"J. Global Optim."},{"issue":"1\u20132","key":"898_CR10","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1002\/mcda.1574","volume":"24","author":"JR Figueira","year":"2017","unstructured":"Figueira, J.R., Fonseca, C.M., Halffmann, P., Klamroth, K., Paquete, L., Ruzika, S., Schulze, B., Stiglmayr, M., Willems, D.: Easy to say they are hard, but hard to see they are easy\u2014towards a categorization of tractable multiobjective combinatorial optimization problems. J. Multi-Criteria Decis. Anal. 24(1\u20132), 82\u201398 (2017). https:\/\/doi.org\/10.1002\/mcda.1574","journal-title":"J. Multi-Criteria Decis. Anal."},{"issue":"3","key":"898_CR11","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1016\/0022-247X(68)90201-1","volume":"22","author":"AM Geoffrion","year":"1968","unstructured":"Geoffrion, A.M.: Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22(3), 618\u2013630 (1968). https:\/\/doi.org\/10.1016\/0022-247X(68)90201-1","journal-title":"J. Math. Anal. Appl."},{"key":"898_CR12","doi-asserted-by":"crossref","unstructured":"Gla\u00dfer, C., Reitwie\u00dfner, C., Schmitz, H., Witek, M.: Approximability and hardness in multi-objective optimization. In: F.\u00a0Ferreira, B.\u00a0L\u00f6we, E.\u00a0Mayordomo, L.\u00a0Mendes\u00a0Gomes (eds.) Programs, Proofs, Processes. CiE 2010, Lecture Notes in Computer Science, vol. 6158, pp. 180\u2013189. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13962-8_20"},{"issue":"3","key":"898_CR13","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s10957-011-9849-8","volume":"150","author":"J Gorski","year":"2011","unstructured":"Gorski, J., Klamroth, K., Ruzika, S.: Connectedness of efficient solutions in multiple objective combinatorial optimization. J. Optim. Theory Appl. 150(3), 475\u2013497 (2011). https:\/\/doi.org\/10.1007\/s10957-011-9849-8","journal-title":"J. Optim. Theory Appl."},{"key":"898_CR14","unstructured":"Halffmann, P., Dietz, T., Ruzika, S.: Partial scalarization: A new way to solve multiobjective problems?. Private Communication (2018)"},{"issue":"4","key":"898_CR15","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1007\/s10898-013-0098-2","volume":"59","author":"AH Hamel","year":"2014","unstructured":"Hamel, A.H., L\u00f6hne, A., Rudloff, B.: Benson type algorithms for linear vector optimization and applications. J. Global Optim. 59(4), 811\u2013836 (2014). https:\/\/doi.org\/10.1007\/s10898-013-0098-2","journal-title":"J. Global Optim."},{"issue":"2","key":"898_CR16","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1137\/060674831","volume":"19","author":"F Heyde","year":"2008","unstructured":"Heyde, F., L\u00f6hne, A.: Geometric duality in multiple objective linear programming. SIAM J. Optim. 19(2), 836\u2013845 (2008). https:\/\/doi.org\/10.1137\/060674831","journal-title":"SIAM J. Optim."},{"issue":"3","key":"898_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119\u2013123 (1988). https:\/\/doi.org\/10.1016\/0020-0190(88)90065-8","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"898_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The hungarian method for the assignment problem. Naval Res. Logist. Q. 2(1\u20132), 83\u201397 (1955). https:\/\/doi.org\/10.1002\/nav.3800020109","journal-title":"Naval Res. Logist. Q."},{"issue":"1","key":"898_CR19","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s10479-006-0072-1","volume":"147","author":"M M\u00fcller-Hannemann","year":"2006","unstructured":"M\u00fcller-Hannemann, M., Weihe, K.: On the cardinality of the pareto set in bicriteria shortest path problems. Ann. Oper. Res. 147(1), 269\u2013286 (2006). https:\/\/doi.org\/10.1007\/s10479-006-0072-1","journal-title":"Ann. Oper. Res."},{"key":"898_CR20","unstructured":"\u00d6zpeynirci, \u00d6.: Approaches for multiobjective combinatorial optimization problems. Ph.D. thesis, Middle East Technical University, Department of Industrial Engineering, Ankara, Turkey (2008)"},{"issue":"12","key":"898_CR21","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.: An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Manag. Sci. 56(12), 2302\u20132315 (2010). https:\/\/doi.org\/10.1287\/mnsc.1100.1248","journal-title":"Manag. Sci."},{"issue":"3","key":"898_CR22","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1287\/ijoc.1090.0342","volume":"22","author":"A Przybylski","year":"2010","unstructured":"Przybylski, A., Gandibleux, X., Ehrgott, M.: A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J. Comput. 22(3), 371\u2013386 (2010). https:\/\/doi.org\/10.1287\/ijoc.1090.0342","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"898_CR23","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.: A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optim. 7(3), 149\u2013165 (2010). https:\/\/doi.org\/10.1016\/j.disopt.2010.03.005","journal-title":"Discrete Optim."},{"issue":"1","key":"898_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1109\/TAC.1963.1105511","volume":"8","author":"L Zadeh","year":"1963","unstructured":"Zadeh, L.: Optimality and non-scalar-valued performance criteria. IEEE Trans. Autom. Control 8(1), 59\u201360 (1963). https:\/\/doi.org\/10.1109\/TAC.1963.1105511","journal-title":"IEEE Trans. Autom. Control"},{"key":"898_CR25","volume-title":"Lectures on Polytopes","author":"GM Ziegler","year":"2012","unstructured":"Ziegler, G.M.: Lectures on Polytopes, vol. 152. Springer, Berlin (2012)"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00898-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-020-00898-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00898-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:13:00Z","timestamp":1615421580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-020-00898-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,11]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["898"],"URL":"https:\/\/doi.org\/10.1007\/s10898-020-00898-9","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2020,3,11]]},"assertion":[{"value":"3 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}