{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:19:46Z","timestamp":1761621586049,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,12]],"date-time":"2021-06-12T00:00:00Z","timestamp":1623456000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,12]],"date-time":"2021-06-12T00:00:00Z","timestamp":1623456000000},"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":["Optim Lett"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We revisit the classic supporting hyperplane illustration of the duality gap for non-convex optimization problems. It is refined by dissecting the duality gap into two terms: the first measures the degree of near-optimality in a Lagrangian relaxation, while the second measures the degree of near-complementarity in the Lagrangian relaxed constraints. We also give an example of how this dissection may be exploited in the design of a solution approach within discrete optimization.<\/jats:p>","DOI":"10.1007\/s11590-021-01764-7","type":"journal-article","created":{"date-parts":[[2021,6,12]],"date-time":"2021-06-12T15:02:47Z","timestamp":1623510167000},"page":"1093-1102","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dissecting the duality gap: the supporting hyperplane interpretation revisited"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9881-4170","authenticated-orcid":false,"given":"Nils-Hassan","family":"Quttineh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2094-7376","authenticated-orcid":false,"given":"Torbj\u00f6rn","family":"Larsson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,12]]},"reference":[{"key":"1764_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-06409-2","volume-title":"Convex Analysis and Minimization Algorithms II","author":"J-B Hiriart-Urruty","year":"1993","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms II. Springer, Berlin (1993)"},{"key":"1764_CR2","volume-title":"Nonlinear Programming: Theory and Algorithms","author":"MS Bazaraa","year":"1993","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms, 2nd edn. Wiley, New York (1993)","edition":"2"},{"key":"1764_CR3","volume-title":"Nonlinear Programming","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)","edition":"2"},{"key":"1764_CR4","volume-title":"Convex Analysis and Optimization","author":"DP Bertsekas","year":"2003","unstructured":"Bertsekas, D.P., Nedi\u0107, A., Ozdaglar, A.E.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003)"},{"key":"1764_CR5","volume-title":"Mathematical Programming: Structures and Algorithms","author":"JF Shapiro","year":"1979","unstructured":"Shapiro, J.F.: Mathematical Programming: Structures and Algorithms. Wiley, New York (1979)"},{"key":"1764_CR6","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.: Global optimality conditions for discrete and nonconvex optimization\u2014with applications to Lagrangian heuristics and column generation. Oper. Res. 54, 436\u2013453 (2006)","journal-title":"Oper. Res."},{"key":"1764_CR7","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1111\/itor.12521","volume":"27","author":"Y Zhao","year":"2020","unstructured":"Zhao, Y., Larsson, T., R\u00f6nnberg, E.: An integer programming column generation principle for heuristic search methods. Int. Trans. Oper. Res. 27, 665\u2013695 (2020)","journal-title":"Int. Trans. Oper. Res."},{"key":"1764_CR8","doi-asserted-by":"crossref","unstructured":"Ngulo, U., Larsson, T., Quttineh, N.-H.: A dissection of the duality gap of set covering problems. In: Neufeld, J.S., Buscher, U., Lasch, R., M\u00f6st, D., Sch\u00f6nberger, J. (eds.) Operations Research Proceedings 2019, Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Dresden 2019. Springer International Publishing, Cham, pp. 175\u2013181 (2020)","DOI":"10.1007\/978-3-030-48439-2_21"},{"key":"1764_CR9","volume-title":"Integer Programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey, L.A.: Integer Programming. Wiley, Hoboken (1998)"},{"issue":"11","key":"1764_CR10","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"JE Beasley","year":"1990","unstructured":"Beasley, J.E.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069\u20131072 (1990)","journal-title":"J. Oper. Res. Soc."},{"issue":"1","key":"1764_CR11","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1002\/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2","volume":"37","author":"JE Beasley","year":"1990","unstructured":"Beasley, J.E.: A Lagrangian heuristic for set-covering problems. Nav. Res. Logist. 37(1), 151\u2013164 (1990)","journal-title":"Nav. Res. Logist."},{"issue":"2","key":"1764_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01581106","volume":"81","author":"S Ceria","year":"1998","unstructured":"Ceria, S., Nobili, P., Sassano, A.: A Lagrangian-based heuristic for large-scale set covering problems. Math. Program. 81(2), 215\u2013228 (1998)","journal-title":"Math. Program."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01764-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01764-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01764-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T06:20:03Z","timestamp":1647843603000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01764-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,12]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["1764"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01764-7","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2021,6,12]]},"assertion":[{"value":"24 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}