{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T12:07:33Z","timestamp":1774958853639,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T00:00:00Z","timestamp":1724112000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T00:00:00Z","timestamp":1724112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-21-1-2262"],"award-info":[{"award-number":["N00014-21-1-2262"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["1933373"],"award-info":[{"award-number":["1933373"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper investigates the potential of Lagrangian relaxations to generate quality bounds on non-dominated images of multiobjective integer programs (MOIPs). Under some conditions on the relaxed constraints, we show that a set of Lagrangian relaxations can provide bounds that coincide with every bound generated by the convex hull relaxation. We also provide a guarantee of the relative quality of the Lagrangian bound at unsupported solutions. These results imply that, if the relaxed feasible region is bounded, some Lagrangian bounds will be strictly better than some convex hull bounds. We demonstrate that there exist Lagrangian multipliers which are sparse, satisfy a complementary slackness property, and generate tight relaxations at supported solutions. However, if all constraints are dualized, a relaxation can never be tight at an unsupported solution. These results characterize the strength of the Lagrangian dual at efficient solutions of an MOIP.<\/jats:p>","DOI":"10.1007\/s10107-024-02121-z","type":"journal-article","created":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T07:03:37Z","timestamp":1724137417000},"page":"683-715","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the strength of Lagrangian duality in multiobjective integer programming"],"prefix":"10.1007","volume":"212","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9615-5175","authenticated-orcid":false,"given":"Matthew","family":"Brun","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8502-8111","authenticated-orcid":false,"given":"Tyler","family":"Perini","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7979-0150","authenticated-orcid":false,"given":"Saumya","family":"Sinha","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0379-741X","authenticated-orcid":false,"given":"Andrew J.","family":"Schaefer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,20]]},"reference":[{"issue":"4","key":"2121_CR1","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1287\/ijoc.2015.0657","volume":"27","author":"N Boland","year":"2015","unstructured":"Boland, N., Charkhgard, H., Savelsbergh, M.: A criterion space search algorithm for biobjective integer programming: The balanced box method. INFORMS J. Comput. 27(4), 735\u2013754 (2015)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"2121_CR2","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1016\/j.ejor.2016.02.037","volume":"260","author":"N Boland","year":"2017","unstructured":"Boland, N., Charkhgard, H., Savelsbergh, M.: 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 (2017)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"2121_CR3","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s10107-014-0763-3","volume":"150","author":"NL Boland","year":"2015","unstructured":"Boland, N.L., Eberhard, A.C.: On the augmented Lagrangian dual for integer programming. Math. Program. 150(2), 491\u2013509 (2015)","journal-title":"Math. Program."},{"issue":"2","key":"2121_CR4","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.ejor.2015.01.035","volume":"244","author":"A Cerqueus","year":"2015","unstructured":"Cerqueus, A., Przybylski, A., Gandibleux, X.: Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems. Eur. J. Oper. Res. 244(2), 417\u2013433 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"12","key":"2121_CR5","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.: An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems. Comput. Oper. Res. 39(12), 2929\u20132943 (2012)","journal-title":"Comput. Oper. Res."},{"key":"2121_CR6","doi-asserted-by":"crossref","unstructured":"Dunbar, A., Sinha, S., Schaefer, A.J.: Relaxations and duality for multiobjective integer programming. Math. Program. (2023)","DOI":"10.1007\/s10107-023-02022-7"},{"key":"2121_CR7","doi-asserted-by":"crossref","unstructured":"Ehrgott, M.: Hard to say it\u2019s easy-four reasons why combinatorial multiobjective programmes are hard. In: Research and Practice in Multiple Criteria Decision Making, pp. 69\u201380. Springer (2000)","DOI":"10.1007\/978-3-642-57311-8_5"},{"key":"2121_CR8","volume-title":"Multicriteria Optimization","author":"M Ehrgott","year":"2005","unstructured":"Ehrgott, M.: Multicriteria Optimization, vol. 491. Springer, Cham (2005)"},{"issue":"1","key":"2121_CR9","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10479-006-0074-z","volume":"147","author":"M Ehrgott","year":"2006","unstructured":"Ehrgott, M.: A discussion of scalarization techniques for multiple objective integer programming. Ann. Oper. Res. 147(1), 343\u2013360 (2006)","journal-title":"Ann. Oper. Res."},{"key":"2121_CR10","doi-asserted-by":"crossref","unstructured":"Ehrgott, M., Gandibleux, X.: Bounds and bound sets for biobjective combinatorial optimization problems. In: Multiple Criteria Decision Making in the New Millennium, pp. 241\u2013253. Springer (2001)","DOI":"10.1007\/978-3-642-56680-6_22"},{"issue":"9","key":"2121_CR11","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.: Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. 34(9), 2674\u20132694 (2007)","journal-title":"Comput. Oper. Res."},{"key":"2121_CR12","doi-asserted-by":"crossref","unstructured":"Everett, H., III.: Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Oper. Res. 11(3), 399\u2013417 (1963)","DOI":"10.1287\/opre.11.3.399"},{"issue":"124","key":"2121_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/crll.1902.124.1","volume":"1902","author":"J Farkas","year":"1902","unstructured":"Farkas, J.: Theorie der einfachen Ungleichungen. Journal f\u00fcr die reine und angewandte Mathematik 1902(124), 1\u201327 (1902)","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"issue":"1\u20132","key":"2121_CR14","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-towards a categorization of tractable multiobjective combinatorial optimization problems. J. Multi-Crit. Decision Anal. 24(1\u20132), 82\u201398 (2017)","journal-title":"J. Multi-Crit. Decision Anal."},{"issue":"1","key":"2121_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"ML Fisher","year":"1981","unstructured":"Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Manage. Sci. 27(1), 1\u201318 (1981)","journal-title":"Manage. Sci."},{"issue":"3","key":"2121_CR16","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1016\/j.ejor.2022.01.047","volume":"302","author":"N Forget","year":"2022","unstructured":"Forget, N., Gadegaard, S.L., Nielsen, L.R.: Warm-starting lower bound set computations for branch-and-bound algorithms for multiobjective integer linear programs. Eur. J. Oper. Res. 302(3), 909\u2013924 (2022)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"2121_CR17","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01442864","volume":"6","author":"P Gordan","year":"1873","unstructured":"Gordan, P.: Ueber die Aufl\u00f6sung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6(1), 23\u201328 (1873)","journal-title":"Math. Ann."},{"key":"2121_CR18","unstructured":"Guignard, M.: Lagrangean relaxation: a short course. JORBEL-Belgian J. Oper. Res. Stat. Comput. Sci. 35(3\u20134), 5\u201321 (1995)"},{"issue":"5\u20136","key":"2121_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1002\/mcda.1780","volume":"29","author":"P Halffmann","year":"2022","unstructured":"Halffmann, P., Sch\u00e4fer, L.E., D\u00e4chert, K., Klamroth, K., Ruzika, S.: 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 (2022)","journal-title":"J. Multi-Criteria Decis. Anal."},{"issue":"3","key":"2121_CR20","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.orl.2006.03.019","volume":"35","author":"HW Hamacher","year":"2007","unstructured":"Hamacher, H.W., Pedersen, C.R., Ruzika, S.: Finding representative systems for discrete bicriterion optimization problems. Oper. Res. Lett. 35(3), 336\u2013344 (2007)","journal-title":"Oper. Res. Lett."},{"key":"2121_CR21","first-page":"533","volume":"2","author":"JN Hooker","year":"2009","unstructured":"Hooker, J.N.: Integer programming duality. Encycl. Optim. 2, 533\u2013543 (2009)","journal-title":"Integer programming duality. Encycl. Optim."},{"key":"2121_CR22","first-page":"1667","volume":"2","author":"JN Hooker","year":"2009","unstructured":"Hooker, J.N.: Integer programming: Lagrangian relaxation. Encycl. Optim. 2, 1667\u20131673 (2009)","journal-title":"Integer programming: Lagrangian relaxation. Encycl. Optim."},{"issue":"1","key":"2121_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1287\/opre.22.1.189","volume":"22","author":"H Isermann","year":"1974","unstructured":"Isermann, H.: Proper efficiency and the linear vector maximum problem. Oper. Res. 22(1), 189\u2013191 (1974)","journal-title":"Oper. Res."},{"issue":"4","key":"2121_CR24","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1287\/ijoc.1110.0476","volume":"24","author":"N Jozefowiez","year":"2012","unstructured":"Jozefowiez, N., Laporte, G., Semet, F.: A generic branch-and-cut algorithm for multiobjective optimization problems: application to the multilabel traveling salesman problem. INFORMS J. Comput. 24(4), 554\u2013564 (2012)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"2121_CR25","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s10732-009-9103-9","volume":"16","author":"T Lust","year":"2010","unstructured":"Lust, T., Teghem, J.: Two-phase Pareto local search for the biobjective traveling salesman problem. Journal of Heuristics 16(3), 475\u2013510 (2010)","journal-title":"Journal of Heuristics"},{"issue":"1","key":"2121_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10898-015-0324-1","volume":"64","author":"E Machuca","year":"2016","unstructured":"Machuca, E., Mandow, L.: Lower bound sets for biobjective shortest path problems. J. Global Optim. 64(1), 63\u201377 (2016)","journal-title":"J. Global Optim."},{"issue":"2","key":"2121_CR27","first-page":"455","volume":"213","author":"G Mavrotas","year":"2009","unstructured":"Mavrotas, G.: Effective implementation of the $$\\varepsilon $$-constraint method in multi-objective mathematical programming problems. Appl. Math. Comput. 213(2), 455\u2013465 (2009)","journal-title":"Appl. Math. Comput."},{"issue":"1","key":"2121_CR28","first-page":"53","volume":"171","author":"G Mavrotas","year":"2005","unstructured":"Mavrotas, G., Diakoulaki, D.: Multi-criteria branch and bound: a vector maximization algorithm for mixed 0\u20131 multiple objective linear programming. Appl. Math. Comput. 171(1), 53\u201371 (2005)","journal-title":"Appl. Math. Comput."},{"issue":"1","key":"2121_CR29","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01585518","volume":"7","author":"RR Meyer","year":"1974","unstructured":"Meyer, R.R.: On the existence of optimal solutions to integer and mixed-integer programming problems. Math. Program. 7(1), 223\u2013235 (1974)","journal-title":"Math. Program."},{"key":"2121_CR30","volume-title":"Integer Programming and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer Programming and Combinatorial Optimization, vol. 191. Springer, Cham (1988)"},{"issue":"12","key":"2121_CR31","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. Manage. Sci. 56(12), 2302\u20132315 (2010)","journal-title":"Manage. Sci."},{"issue":"1","key":"2121_CR32","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., Savelsbergh, M.: A criterion space method for biobjective mixed integer programming: the boxed line method. INFORMS J. Comput. 32(1), 16\u201339 (2020)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"2121_CR33","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)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"2121_CR34","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. Discret. Optim. 7(3), 149\u2013165 (2010)","journal-title":"Discret. Optim."},{"issue":"2","key":"2121_CR35","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1080\/16073606.1978.9631564","volume":"3","author":"M Sinclair","year":"1978","unstructured":"Sinclair, M.: Augmented Lagrangean relaxations in general mixed integer programming. Quaest. Math. 3(2), 115\u2013146 (1978)","journal-title":"Quaest. Math."},{"issue":"3","key":"2121_CR36","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1287\/ijoc.1070.0260","volume":"20","author":"F Sourd","year":"2008","unstructured":"Sourd, F., Spanjaard, O.: A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS J. Comput. 20(3), 472\u2013484 (2008)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"2121_CR37","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/j.ejor.2018.01.026","volume":"268","author":"B Soylu","year":"2018","unstructured":"Soylu, B.: The search-and-remove algorithm for biobjective mixed-integer linear programming problems. Eur. J. Oper. Res. 268(1), 281\u2013299 (2018)","journal-title":"Eur. J. Oper. Res."},{"key":"2121_CR38","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, G.B.: An exact algorithm for biobjective mixed integer linear programming problems. Comput. Oper. Res. 72, 204\u2013213 (2016)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"2121_CR39","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1287\/ijoc.2020.0953","volume":"33","author":"S Tamby","year":"2021","unstructured":"Tamby, S., Vanderpooten, D.: Enumeration of the nondominated set of multiobjective discrete optimization problems. INFORMS J. Comput. 33(1), 72\u201385 (2021)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"2121_CR40","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/j.cor.2012.08.003","volume":"40","author":"T Vincent","year":"2013","unstructured":"Vincent, T., Seipp, F., Ruzika, S., Przybylski, A., Gandibleux, X.: Multiple objective branch and bound for mixed 0\u20131 linear programming: corrections and improvements for the biobjective case. Comput. Oper. Res. 40(1), 498\u2013509 (2013)","journal-title":"Comput. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02121-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02121-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02121-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:03:15Z","timestamp":1750176195000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02121-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,20]]},"references-count":40,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2121"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02121-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,20]]},"assertion":[{"value":"7 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflicts of interest to report.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}