{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T19:16:21Z","timestamp":1726514181377},"reference-count":67,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p> This paper provides a novel framework for solving multiobjective discrete optimization problems with an arbitrary number of objectives. Our framework represents these problems as network models, in that enumerating the Pareto frontier amounts to solving a multicriteria shortest-path problem in an auxiliary network. We design techniques for exploiting network models in order to accelerate the identification of the Pareto frontier, most notably a number of operations to simplify the network by removing nodes and arcs while preserving the set of nondominated solutions. We show that the proposed framework yields orders-of-magnitude performance improvements over existing state-of-the-art algorithms on five problem classes containing both linear and nonlinear objective functions. <\/jats:p><jats:p> Summary of Contribution: Multiobjective optimization has a long history of research with applications in several domains. Our paper provides an alternative modeling and solution approach for multiobjective discrete optimization problems by leveraging graphical structures. Specifically, we encode the decision space of a problem as a layered network and propose graph reduction operators to preserve only solutions whose image are part of the Pareto frontier. The nondominated solutions can then be extracted through shortest-path algorithms on such a network. Numerical results comparing our method with state-of-the-art approaches on several problem classes, including the knapsack, set covering, and the traveling salesperson problem (TSP), suggest orders-of-magnitude runtime speed-ups for exactly enumerating the Pareto frontier, especially when the number of objective functions grows. <\/jats:p>","DOI":"10.1287\/ijoc.2021.1066","type":"journal-article","created":{"date-parts":[[2021,11,24]],"date-time":"2021-11-24T18:16:34Z","timestamp":1637777794000},"page":"990-1005","source":"Crossref","is-referenced-by-count":5,"title":["Network Models for Multiobjective Discrete Optimization"],"prefix":"10.1287","volume":"34","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-5566-5224","authenticated-orcid":false,"given":"David","family":"Bergman","sequence":"first","affiliation":[{"name":"Department of Operations and Information Management, University of Connecticut, Stamford, Connecticut 06901;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9276-3755","authenticated-orcid":false,"given":"Merve","family":"Bodur","sequence":"additional","affiliation":[{"name":"Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-1439-5205","authenticated-orcid":false,"given":"Carlos","family":"Cardonha","sequence":"additional","affiliation":[{"name":"Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06269;"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-5993-4295","authenticated-orcid":false,"given":"Andre A.","family":"Cire","sequence":"additional","affiliation":[{"name":"Department of Management, Scarborough & Rotman School of Management, University of Toronto, Toronto, Ontario M1C 1A4, Canada"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.09.009"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2017.0804"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-44953-1_6"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42849-9"},{"key":"B5","volume-title":"Dynamic Programming and Optimal Control","volume":"1","author":"Bertsekas DP","year":"2017","edition":"4"},{"key":"B6","volume-title":"Introduction to Linear Optimization","volume":"6","author":"Bertsimas D","year":"1997"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584332"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0093-3"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2016.02.037"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(02)00112-0"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90318-6"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1221"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-014-0205-z"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.10.034"},{"key":"B18","volume-title":"Supply Chain Management with APO: Structures, Modelling Approaches and Implementation of MySAP SCM 4.1","author":"Dickersbach JT","year":"2015","edition":"2"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-54157-0_14"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-0074-z"},{"key":"B21","doi-asserted-by":"crossref","unstructured":"Ehrgott M, Gandibleux X, Przybylski A (2016) Exact Methods for Multi-objective Combinatorial Optimisation. Multiple Criteria Decision Analysis, 2nd ed. (Springer), 817\u2013850.","DOI":"10.1007\/978-1-4939-3094-4_19"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.06.026"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-013-9551-x"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1080\/02331938208842786"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2014.03.110"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0846"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.05.017"},{"issue":"1","key":"B30","first-page":"296","volume":"1","author":"Haimes Y","year":"1971","journal-title":"IEEE Trans. Systems Man Cybernetics"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(86)90092-5"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38171-3_7"},{"key":"B33","unstructured":"IBM ILOG (2020) CPLEX Optimization Studio 12.10 user manual. https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio."},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0891"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1110.0476"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.08.001"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(200002)47:1<57::AID-NAV4>3.0.CO;2-4"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.03.031"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(82)90182-5"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.029"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-012-9955-7"},{"key":"B44","doi-asserted-by":"crossref","unstructured":"Lust T, Teghem J (2010) The Multiobjective Traveling Salesman Problem: A Survey and a New Approach (Springer, Berlin Heidelberg), 119\u2013141.","DOI":"10.1007\/978-3-642-11218-8_6"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2011.00840.x"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0413"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(97)00077-5"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2005.01.038"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1145\/321043.321046"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2016.12"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.10.023"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-013-0364-y"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0856"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0887"},{"issue":"2","key":"B55","first-page":"461","volume":"32","author":"Pettersson W","year":"2020","journal-title":"INFORMS J. Comput."},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2017.01.032"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-0058-z"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.11.032"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2011.07.067"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1050.0413"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0260"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591870"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2018.02.001"},{"key":"B64","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2013.1802"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(03)00255-8"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.2478\/v10006-007-0023-2"},{"key":"B68","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.12.047"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.1007\/BF00934322"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.08.003"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-018-1267-5"},{"key":"B72","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"B73","doi-asserted-by":"publisher","DOI":"10.1016\/S0933-3657(99)00049-4"},{"key":"B74","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2011.03.001"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2021.1066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T13:47:33Z","timestamp":1680443253000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2021.1066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.1287\/ijoc.2021.1066"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2021.1066","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}  <script>parent.window.postMessage('ixistenz.url:https://api.crossref.org/works/10.1287%2FIJOC.2021.1066', '*'); </script> <div id='browserdiffcontainer' style='position: fixed; right: 10px; top: 10vh; min-width: 60px;  border: 1px solid white; background: rgb(251, 189, 0);; opacity: 0.9; font-family: helvetica, arial, sans serif;  font-size: 12px; z-index: 20001; padding-bottom: 20px;'><div onclick="toggle('browserdiffcontainerlist'); return false;" style='background: rgb(151, 89, 0);; color: white; '><strong>&nbsp; <span class='glyphicon glyphicon-minus'></span> NODES</strong></div><div id='browserdiffcontainerlist' style='padding-left: 10px; padding-right: 5px; max-height: 50vh; overflow: auto; '></div></div>
<script>
function toggle( divname ) {
  var x = document.getElementById( divname );
  if (x.style.display === 'none') {
    x.style.display = 'block';
  } else {
    x.style.display = 'none';
  }
} </script>