{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:07Z","timestamp":1740144487837,"version":"3.37.3"},"reference-count":29,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T00:00:00Z","timestamp":1723680000000},"content-version":"vor","delay-in-days":45,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,6,8]]},"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>This paper introduces a parallel implementation of an exact two-phase method for solving the bi-objective knapsack problem on a CPU-GPU system. We utilize the Branch-and-Bound procedure in both phases, along with a highly efficient reduction technique to generate all efficient solutions. However, in the first phase, we focus on identifying all supported extreme efficient solutions, followed by reducing the dimension of the problem using an object efficiency reduction algorithm. The second phase is responsible for generating all unsupported efficient solutions. We develop a combined algorithm incorporating both phases, which is implemented in the CUDA language. Our study investigates the impact of parallel computing performance on various numerical instances compared to other exact methods in the literature. Additionally, we confirm the effectiveness of our proposed parallel-solving method by testing uncorrelated instances.<\/jats:p>","DOI":"10.1051\/ro\/2024125","type":"journal-article","created":{"date-parts":[[2024,6,14]],"date-time":"2024-06-14T19:04:33Z","timestamp":1718391873000},"page":"3347-3367","source":"Crossref","is-referenced-by-count":0,"title":["Parallel implementation of an exact two-phase method for the biobjective knapsack problem"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-5937-4758","authenticated-orcid":false,"given":"Khadidja","family":"Chaabane","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sadek","family":"Bouroubi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0112-4737","authenticated-orcid":false,"given":"Younes","family":"Djellouli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,8,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1287\/mnsc.25.1.73","volume":"25","author":"Aneja","year":"1979","journal-title":"Manag. Sci."},{"key":"R2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejor.2008.07.047","volume":"198","author":"Bazgan","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"R3","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.cor.2007.09.009","volume":"36","author":"Bazgan","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Bowman V.J., On the relationship of the tchebycheff norm and the efficient frontier of multiple-criteria objectives. In: Multiple Criteria Decision Making: Proceedings of a Conference Jouy-en-Josas, France May 21\u201323, 1975. Springer (1976) 76\u201386.","DOI":"10.1007\/978-3-642-87563-2_5"},{"key":"R5","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.cor.2011.03.014","volume":"39","author":"Boyer","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"R6","doi-asserted-by":"crossref","first-page":"1865","DOI":"10.1016\/S0305-0548(02)00112-0","volume":"30","author":"Captivo","year":"2003","journal-title":"Comput. Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.ejor.2015.01.035","volume":"244","author":"Cerqueus","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"R8","doi-asserted-by":"crossref","first-page":"1739","DOI":"10.1111\/itor.12285","volume":"25","author":"Daoud","year":"2018","journal-title":"Int. Trans. Oper. Res."},{"key":"R9","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s002910000046","volume":"22","author":"Ehrgott","year":"2000","journal-title":"OR-Spektrum"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Ehrgott M. and Gandibleux X., Multiobjective Combinatorial Optimization\u2013Theory, Methodology, and Applications. Springer (2002) 369\u2013444.","DOI":"10.1007\/0-306-48107-3_8"},{"key":"R11","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.jpdc.2004.10.004","volume":"65","author":"El Baz","year":"2005","journal-title":"J. Parallel Distr. Comput."},{"key":"R12","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10589-013-9551-x","volume":"56","author":"Figueira","year":"2013","journal-title":"Comput. Optim. Appl."},{"key":"R13","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.ejor.2009.06.024","volume":"203","author":"Florios","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"R14","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1023\/A:1009682532542","volume":"6","author":"Gandibleux","year":"2000","journal-title":"J. Heuristics"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Gandibleux X., Mezdaoui N. and Fr\u00e9ville A., A tabu search procedure to solve multiobjective combinatorial optimization problems. In: Advances in Multiple Objective and Goal Programming: Proceedings of the Second International Conference on Multi-Objective Programming and Goal Programming, Torremolinos, Spain, May 16\u201318, 1996. Springer (1997) 291\u2013300.","DOI":"10.1007\/978-3-642-46854-4_32"},{"key":"R16","unstructured":"Gandibleux X., Soleilhac G., Przybylski A., Lucas F., Ruzika S. and Halffmann P., voptsolver, a get and run solver of multiobjective linear optimization problems built on julia and jump. In Vol. 88 MCDM2017: 24th International Conference on Multiple Criteria Decision Making (2017)."},{"key":"R17","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1287\/opre.13.6.879","volume":"13","author":"Glover","year":"1965","journal-title":"Oper. Res."},{"key":"R18","unstructured":"Jorge J., Nouvelles propositions pour la r\u00e9solution exacte du sac-\u00e0-dos multi-objectif unidimensionnel en variables binaires, Ph.D. thesis, Universit\u00e9 de Nantes (2010)."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Lalami M.E. and El-Baz D., Gpu implementation of the branch and bound method for knapsack problems. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. IEEE (2012) 1769\u20131777.","DOI":"10.1109\/IPDPSW.2012.219"},{"key":"R20","doi-asserted-by":"crossref","first-page":"1985","DOI":"10.1016\/S0167-8191(96)00085-3","volume":"22","author":"Lou","year":"1997","journal-title":"Parallel Comput."},{"key":"R21","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1287\/mnsc.34.5.633","volume":"34","author":"Martello","year":"1988","journal-title":"Manag. Sci."},{"key":"R22","unstructured":"Martello S. and Toth P., Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc. (1990)."},{"key":"R23","unstructured":"Nvidia, Cuda C++ Programming Guide: 11.7. 0 (2022)."},{"key":"R24","first-page":"461","volume":"32","author":"Pettersson","year":"2020","journal-title":"INFORMS J. Comput."},{"key":"R25","doi-asserted-by":"crossref","first-page":"e4954","DOI":"10.1002\/cpe.4954","volume":"31","author":"Shen","year":"2019","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"R26","unstructured":"Ulungu E.L., Optimisation Combinatoire multicrit\u00e8re: D\u00e9termination de l\u2019ensemble des solutions efficaces et m\u00e9thodes interactives, Ph.D. thesis, Facult\u00e9 des Sciences, Universit\u00e9 de Mons-Hainaut, Mons, Belgique (1993)."},{"key":"R27","first-page":"149","volume":"20","author":"Ulungu","year":"1995","journal-title":"Found. Comput. Decis. Sci."},{"key":"R28","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/(SICI)1099-1360(199907)8:4<221::AID-MCDA247>3.0.CO;2-O","volume":"8","author":"Ulungu","year":"1999","journal-title":"J. Multi-Criteria Decis. Anal."},{"key":"R29","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1023\/A:1008258310679","volume":"12","author":"Vis\u00e9e","year":"1998","journal-title":"J. Glob. Optim."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024125\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T08:08:52Z","timestamp":1723709332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":29,"journal-issue":{"issue":"4"},"alternative-id":["ro230270"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024125","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,7]]}}}