{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:42:38Z","timestamp":1764783758851},"reference-count":27,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> The hypervolume subset selection problem consists of finding a subset, with a given cardinality k, of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically efficient algorithms are required. In this article, two new formulations are provided for the two-dimensional variant of this problem. The first is a (linear) integer programming formulation that can be solved by solving its linear programming relaxation. The second formulation is a k-link shortest path formulation on a special digraph with the Monge property that can be solved by dynamic programming in [Formula: see text] time. This improves upon the result of [Formula: see text] in Bader ( 2009 ), and slightly improves upon the result of [Formula: see text] in Bringmann et\u00a0al. ( 2014b ), which was developed independently from this work using different techniques. Numerical results are shown for several values of n and k. <\/jats:p>","DOI":"10.1162\/evco_a_00157","type":"journal-article","created":{"date-parts":[[2015,7,2]],"date-time":"2015-07-02T14:23:56Z","timestamp":1435847036000},"page":"411-425","source":"Crossref","is-referenced-by-count":52,"title":["Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms"],"prefix":"10.1162","volume":"24","author":[{"given":"Tobias","family":"Kuhn","sequence":"first","affiliation":[{"name":"Mathematical Institute, University of Kaiserslautern, Germany"}]},{"given":"Carlos M.","family":"Fonseca","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, Portugal"}]},{"given":"Lu\u00eds","family":"Paquete","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, Portugal"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Koblenz-Landau, Campus Koblenz, Germany"}]},{"given":"Miguel M.","family":"Duarte","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, Portugal"}]},{"given":"Jos\u00e9 Rui","family":"Figueira","sequence":"additional","affiliation":[{"name":"CEG-IST, Instituto Superior T\u00e9cnico, Universidade de Lisboa, Portugal"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840359"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574380"},{"key":"B4","author":"Bader J.","year":"2009","journal-title":"Hypervolume-based search for multiobjective optimization: Theory and methods"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00009"},{"key":"B6","volume-title":"Linear programming and network flows","author":"Bazaraa M. S.","year":"2011"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.08.008"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01020-0_6"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00012"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_51"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598276"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19893-9_9"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36970-8_37"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35533-2_3"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2003.1299373"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2007.15.1.1"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2002.1007013"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2003.810755"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2003.1299401"},{"key":"B20","first-page":"869","volume":"1917","author":"Knowles J.","year":"2000","journal-title":"Parallel Problem Solving from Nature"},{"key":"B21","volume-title":"Integer and combinatorial optimization","author":"Nemhauser G. L.","year":"1999"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-005-5494-4"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050128"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1162\/106365600568202"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88908-3_14"},{"key":"B26","first-page":"832","volume":"3242","author":"Zitzler E.","year":"2004","journal-title":"Parallel Problem Solving from Nature"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056872"},{"key":"B28","first-page":"7:117","author":"Zitzler E.","year":"2003","journal-title":"IEEE Transactions on Evolutionary Computation"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:41Z","timestamp":1615586321000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/24\/3\/411-425\/1022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1162\/EVCO_a_00157"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00157","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}