.png){kind=icon}
.png){kind=icon}
Return
Bi-dimensional knapsack problems with one soft constraint
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2016.07.012.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we consider bi-dimensional knapsack problems with a soft constraint, i.e., a constraint for which the right-hand side is not precisely fixed or uncertain. We reformulate these problems as bi-objective knapsack problems, where the soft constraint is relaxed and interpreted as an additional objective function. In this way, a sensitivity analysis for the bi-dimensional knapsack problem can be performed: The trade-off between constraint satisfaction, on the one hand, and the original objective value, on the other hand, can be analyzed. It is shown that a dynamic programming based solution approach for the bi-objective knapsack problem can be adapted in such a way that a representation of the nondominated set is obtained at moderate extra cost. In this context, we are particularly interested in representations of that part of the nondominated set that is in a certain sense close to the constrained optimum in the objective space. We discuss strategies for bound computations and for handling negative cost coefficients, which occur through the transformation. Numerical results comparing the bi-dimensional and bi-objective approaches are presented. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Bi-dimensional knapsack problem
Bi-objective knapsack problem
Sensitivity analysis
Soft constraints
Dynamic programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
View more organizations