Multiobjective Knapsack Problem with Equity Concerns

Abstract

In this paper, a multi-objective mathematical modeling approach has been developed for resource distribution problem which has equity concerns. We assume that the preference model of the decision maker satisfies properties related to inequity-aversion, hence we focus on finding nondominated solutions in line with the properties of inequity-averse preferences, namely the equitably efficient solutions. We propose a dynamic programming (DP) based algorithm, which exploits different lower and upper bounds to eliminate partial solutions that will not lead to equitably efficient solutions. In addition to the lower bounds previously discussed in the literature, we define a new lower bound and demonstrate its effectiveness. We perform experiments to show and discuss the performances of the DP algorithm and another well-known exact approach, the epsilon constraint method, for bi-objective settings. We also provide results of the epsilon constraint method for three-objective settings.

Keywords

• Multi-objective knapsack problem
• Equitable preferences
• Equitable efficiency
• Dynamic programming
• Epsilon-constraint approach