.png){kind=icon}
Return
Bi-objective knapsack problem with conflicts
.png){kind=icon}
OA
AI
DOI：10.1007/s10479-025-06792-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this work we propose a bi-objective variant of the well-known 0/1 Knapsack Problem, that finds application in cases in which some item pairs may be seen as mutually conflicting. Previous variants considered in this scenario proposed to either avoid all conflicts, or to deal with them by considering the payment of appropriate penalty costs. We propose a different approach where the maximization of the profit and the minimization of the accepted conflicts are considered two different objective functions. We aim at identifying all Pareto-optimal solutions, so that a decision maker may choose a posteriori the optimal trade-off. We propose an exact resolution method based on the $$\epsilon $$ -constraint approach. Computational results on a wide set of instances show that our approach can be used in practice to identify and analyze their Pareto front.
Keywords:
Multi-objective optimization
Knapsack problem
Conflicts
\(\epsilon \) -constraint
AUGMECON2
Journal
IF:
4.5
Papers:
8.1K
Citations:
2.1W
Organization
Cited Papers
No cited papers available