Scholarlink

<p>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 <i>a posteriori</i> the optimal trade-off. We propose an exact resolution method based on the <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\epsilon \)</EquationSource> </InlineEquation>-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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Bi-objective knapsack problem with conflicts

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年10月3日

查看全文
  • Donatella Granata,
  • Andrea Raiconi

摘要

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.