{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T14:44:38Z","timestamp":1740149078786,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003945","name":"Link\u00f6ping University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003945","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Lagrangian relaxation is a common and often successful way to approach computationally challenging single-objective discrete optimization problems with complicating side constraints. Its aim is often twofold; first, it provides bounds for the optimal value, and, second, it can be used to heuristically find near-optimal feasible solutions, the quality of which can be assessed by the bounds. We consider bi-objective discrete optimization problems with complicating side constraints and extend this Lagrangian bounding and heuristic principle to such problems. The Lagrangian heuristic here produces non-dominated candidates for points on the Pareto frontier, while the bounding forms a polyhedral outer approximation of the Pareto frontier, which can be used to assess the quality of the candidate points. As an illustration example we consider a facility location problem in which both CO<jats:sub>2<\/jats:sub>\u00a0emission and cost should be minimized. The computational results are very encouraging, both with respect to bounding and the heuristically found non-dominated solutions. In particular, the Lagrangian bounding is much stronger than the outer approximation given by the Pareto frontier of the problem\u2019s linear programming relaxation.<\/jats:p>","DOI":"10.1007\/s12351-024-00820-1","type":"journal-article","created":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T12:02:17Z","timestamp":1710158537000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Lagrangian bounding and heuristic principle for bi-objective discrete optimization"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2094-7376","authenticated-orcid":false,"given":"Torbj\u00f6rn","family":"Larsson","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9881-4170","authenticated-orcid":false,"given":"Nils-Hassan","family":"Quttineh","sequence":"additional","affiliation":[]},{"given":"Ida","family":"\u00c5kerholm","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,11]]},"reference":[{"key":"820_CR1","unstructured":"\u00c5kerholm I (2022) Lagrangian bounding and heuristics for bi-objective discrete optimisation. Bachelor thesis LiTH-MAT-EX-2022\/16-SE, Department of Mathematics, Link\u00f6ping University, Sweden"},{"issue":"1","key":"820_CR2","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/0377-2217(84)90211-X","volume":"15","author":"J Barcelo","year":"1984","unstructured":"Barcelo J, Casanovas J (1984) A heuristic Lagrangian algorithm for the capacitated plant location problem. Eur J Oper Res 15(1):212\u2013226","journal-title":"Eur J Oper Res"},{"issue":"1","key":"820_CR3","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0377-2217(93)90118-7","volume":"65","author":"JE Beasley","year":"1993","unstructured":"Beasley JE (1993) Lagrangean heuristics for location problems. Eur J Oper Res 65(1):383\u2013399","journal-title":"Eur J Oper Res"},{"issue":"10","key":"820_CR4","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1287\/mnsc.27.10.1120","volume":"27","author":"GR Bitran","year":"1981","unstructured":"Bitran GR, Chandru V, Sempolinski DE, Shapiro JF (1981) Inverse optimization: an application to the capacitated plant location problem. Manag Sci 27(10):1120\u20131141","journal-title":"Manag Sci"},{"issue":"1","key":"820_CR5","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 (2015) Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems. Eur J Oper Res 244(1):417\u2013433","journal-title":"Eur J Oper Res"},{"issue":"1","key":"820_CR6","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/0377-2217(91)90261-S","volume":"50","author":"G Cornuejols","year":"1991","unstructured":"Cornuejols G, Sridharan R, Thizy JM (1991) A comparison of heuristics and relaxations for the capacitated plant location problem. Eur J Oper Res 50(1):280\u2013297","journal-title":"Eur J Oper Res"},{"issue":"1","key":"820_CR7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0377-2217(02)00829-9","volume":"151","author":"MJ Cortinhal","year":"2003","unstructured":"Cortinhal MJ, Captivo ME (2003) Upper and lower bounds for the single source capacitated location problem. Eur J Oper Res 151(1):333\u2013351","journal-title":"Eur J Oper Res"},{"issue":"12","key":"820_CR8","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(12):2929\u20132943","journal-title":"Comput Oper Res"},{"issue":"1","key":"820_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.orl.2017.11.011","volume":"46","author":"R Dai","year":"2018","unstructured":"Dai R, Charkhgard H (2018) A two-stage approach for bi-objective integer linear programming. Oper Res Lett 46(1):81\u201387","journal-title":"Oper Res Lett"},{"issue":"1","key":"820_CR10","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 scalarisation techniques for multiple objective integer programming. Ann Oper Res 147(1):343\u2013360. https:\/\/doi.org\/10.1007\/s10479-006-0074-z","journal-title":"Ann Oper Res"},{"issue":"1","key":"820_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"M Ehrgott","year":"2000","unstructured":"Ehrgott M, Gandibleux X (2000) A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22(1):425\u2013460","journal-title":"OR Spektrum"},{"issue":"1","key":"820_CR12","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(1):2674\u20132694","journal-title":"Comput Oper Res"},{"issue":"7","key":"820_CR13","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1016\/j.apm.2009.10.005","volume":"34","author":"RZ Farahani","year":"2010","unstructured":"Farahani RZ, SteadieSeifi M, Asgari N (2010) Multiple criteria facility location problems: a survey. Appl Math Model 34(7):1689\u20131709","journal-title":"Appl Math Model"},{"issue":"6","key":"820_CR14","doi-asserted-by":"publisher","first-page":"3479","DOI":"10.1111\/itor.13180","volume":"30","author":"S Fotedar","year":"2023","unstructured":"Fotedar S, Str\u00f6mberg A-B, Almgren T (2023) Bi-objective optimization of the tactical allocation of job types to machines: mathematical modeling, theoretical analysis, and numerical tests. Int Trans Oper Res 30(6):3479\u20133507","journal-title":"Int Trans Oper Res"},{"issue":"4","key":"820_CR15","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1504\/IJOR.2021.117078","volume":"41","author":"S Gholipour","year":"2021","unstructured":"Gholipour S, Salehian F, Lamouchi H, Mina H (2021) A green closed-loop supply chain network: a bi-objective mixed integer linear programming model. Int J Oper Res 41(4):492\u2013513","journal-title":"Int J Oper Res"},{"issue":"9","key":"820_CR16","doi-asserted-by":"publisher","first-page":"1572","DOI":"10.1080\/00207721.2013.823526","volume":"46","author":"I Giagkiozis","year":"2015","unstructured":"Giagkiozis I, Purshouse RC, Fleming PJ (2015) An overview of population-based algorithms for multi-objective optimisation. Int J Syst Sci 46(9):1572\u20131599","journal-title":"Int J Syst Sci"},{"issue":"5\u20136","key":"820_CR18","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, Klamroth K, Ruzika S (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. https:\/\/doi.org\/10.1002\/mcda.1780","journal-title":"J Multi-Criteria Decis Anal"},{"key":"820_CR19","doi-asserted-by":"crossref","unstructured":"Harris I, Mumford CL, Naim MM (2011) An evolutionary bi-objective approach to the capacitated facility location problem with cost and $$\\rm CO_2$$ emissions. In: Proceedings of the 13th genetic and evolutionary computation conference, GECCO\u201911. ACM, pp\u00a0697\u2013704","DOI":"10.1145\/2001576.2001672"},{"issue":"1","key":"820_CR20","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/S0377-2217(98)00008-3","volume":"113","author":"K Holmberg","year":"1999","unstructured":"Holmberg K, R\u00f6nnqvist M, Yuan D (1999) An exact algorithm for the capacitated facility location problems with single sourcing. Eur J Oper Res 113(1):544\u2013599","journal-title":"Eur J Oper Res"},{"issue":"5","key":"820_CR21","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1057\/jors.1986.84","volume":"37","author":"JG Klincewicz","year":"1986","unstructured":"Klincewicz JG, Luss H (1986) A Lagrangian relaxation heuristic for capacitated facility location with single-source constraints. J Oper Res Soc 37(5):495\u2013500","journal-title":"J Oper Res Soc"},{"issue":"3","key":"820_CR22","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/opre.1060.0292","volume":"54","author":"T Larsson","year":"2006","unstructured":"Larsson T, Patriksson M (2006) Global optimality conditions for discrete and nonconvex optimization\u2014with applications to Lagrangian heuristics and column generation. Oper Res 54(3):436\u2013453","journal-title":"Oper Res"},{"key":"820_CR23","volume":"10","author":"T Larsson","year":"2023","unstructured":"Larsson T, Quttineh N-H (2023) One-parametric analysis of column-oriented linear programs. Oper Res Perspect 10:100278","journal-title":"Oper Res Perspect"},{"key":"820_CR24","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.cor.2016.02.006","volume":"72","author":"M Leitner","year":"2016","unstructured":"Leitner M, Ljubi\u0107 I, Sinnl M, Werner A (2016) ILP heuristics and a new exact method for bi-objective 0\/1 ILPs: application to FTTx-network design. Comput Oper Res 72:128\u2013146","journal-title":"Comput Oper Res"},{"key":"820_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2020.106382","volume":"93","author":"Q Liu","year":"2020","unstructured":"Liu Q, Li X, Liu H, Guo Z (2020) Multi-objective metaheuristics for discrete optimization problems: a review of the state-of-the-art. Appl Soft Comput 93:106382","journal-title":"Appl Soft Comput"},{"issue":"1","key":"820_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0377-2217(02)00484-8","volume":"149","author":"AL Medaglia","year":"2003","unstructured":"Medaglia AL, Fang S-C (2003) A genetic-based framework for solving (multi-criteria) weighted matching problems. Eur J Oper Res 149(1):77\u2013101","journal-title":"Eur J Oper Res"},{"issue":"1","key":"820_CR27","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1016\/j.ejor.2022.07.044","volume":"306","author":"M Mesquita-Cunha","year":"2022","unstructured":"Mesquita-Cunha M, Figueira JR, Barbosa-Povoa AP (2022) New $$\\epsilon $$-constraint methods for multi-objective integer linear programming: a Pareto front representation approach. Eur J Oper Res 306(1):286\u2013307","journal-title":"Eur J Oper Res"},{"issue":"1","key":"820_CR28","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/s11750-010-0162-8","volume":"20","author":"E Olivares-Benitez","year":"2012","unstructured":"Olivares-Benitez E, Gonzalez-Velarde JL, Rios-Mercado RZ (2012) A supply chain design problem with facility location and bi-objective transportation choices. TOP 20(1):729\u2013753. https:\/\/doi.org\/10.1007\/s11750-010-0162-8","journal-title":"TOP"},{"issue":"4","key":"820_CR29","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1287\/ijoc.2018.0856","volume":"31","author":"SN Parragh","year":"2019","unstructured":"Parragh SN, Tricoire F (2019) Branch-and-bound for bi-objective integer programming. INFORMS J Comput 31(4):805\u2013822","journal-title":"INFORMS J Comput"},{"issue":"3","key":"820_CR30","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0305-0548(87)90022-0","volume":"14","author":"H Pirkul","year":"1987","unstructured":"Pirkul H (1987) Efficient algorithms for the capacitated concentrator location problem. Comput Oper Res 14(3):197\u2013208","journal-title":"Comput Oper Res"},{"key":"820_CR32","doi-asserted-by":"crossref","unstructured":"Shor NZ (1985) Minimization methods for non-differentiable functions, translated from the Russian by K.C.\u00a0Kiwiel and A.\u00a0Ruszczy\u0144ski. Springer, Berlin","DOI":"10.1007\/978-3-642-82118-9"},{"issue":"3","key":"820_CR33","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0377-2217(93)90219-D","volume":"66","author":"R Sridharan","year":"1993","unstructured":"Sridharan R (1993) A Lagrangian heuristic for the capacitated plant location problem with single source constraints. Eur J Oper Res 66(3):305\u2013312","journal-title":"Eur J Oper Res"},{"key":"820_CR34","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-030-34910-3_15","volume-title":"Numerical nonsmooth optimization: state of the art algorithms","author":"A-B Str\u00f6mberg","year":"2020","unstructured":"Str\u00f6mberg A-B, Larsson T, Patriksson M (2020) Mixed-integer linear optimization: primal-dual relations and dual subgradient and cutting-plane methods. In: Bagirov AM, Gaudioso M, Karmitsa N, M\u00e4kel\u00e4 MM, Taheri S (eds) Numerical nonsmooth optimization: state of the art algorithms. Springer, Cham, pp 499\u2013547"},{"key":"820_CR35","volume-title":"Integer programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey LA (1998) Integer programming. Wiley, New York"},{"key":"820_CR36","doi-asserted-by":"publisher","DOI":"10.1155\/2017\/6350562","author":"D Zhang","year":"2017","unstructured":"Zhang D, Zou F, Li S, Zhou L (2017) Green supply chain network design with economies of scale and environmental concerns. J Adv Transp. https:\/\/doi.org\/10.1155\/2017\/6350562","journal-title":"J Adv Transp"},{"key":"820_CR37","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/BFb0056872","volume-title":"Parallel problem solving from nature\u2014-PPSN V","author":"E Zitzler","year":"1998","unstructured":"Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms\u2014a comparative case study. In: Eiben AE, B\u00e4ck T, Schoenauer M, Schwefel H-P (eds) Parallel problem solving from nature\u2014-PPSN V. Springer, Berlin, pp 292\u2013301"}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-024-00820-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12351-024-00820-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-024-00820-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T13:20:17Z","timestamp":1720790417000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12351-024-00820-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,11]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["820"],"URL":"https:\/\/doi.org\/10.1007\/s12351-024-00820-1","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"type":"print","value":"1109-2858"},{"type":"electronic","value":"1866-1505"}],"subject":[],"published":{"date-parts":[[2024,3,11]]},"assertion":[{"value":"15 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 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":"The authors declare that they have no competing interest that could have influenced the research reported in this paper. This research was not supported by any specific funding.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"14"}}