Issue |
RAIRO-Oper. Res.
Volume 58, Number 4, July-August 2024
|
|
---|---|---|
Page(s) | 3347 - 3367 | |
DOI | https://doi.org/10.1051/ro/2024125 | |
Published online | 15 August 2024 |
Parallel implementation of an exact two-phase method for the biobjective knapsack problem
1
LIFORCE Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar 16111, Algiers, Algeria
2
AMCD-RO Laboratory, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, 16111 Bab Ezzouar, Algiers, Algeria
* Corresponding author: khadidjachaabane03@gmail.com
Received:
8
April
2023
Accepted:
8
June
2024
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.
Mathematics Subject Classification: 90C05 / 90C25 / 90C29 / 65K05
Key words: Multi-objective optimization / efficient solution / combinatorial optimization / GPU computing / CUDA
© The authors. Published by EDP Sciences, ROADEF, SMAI 2024
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.