Minimum Complete Pareto Front of the Biobjective 0-1 Knapsack Problem

Abstract

We propose an exact algorithm that constructs the minimum complete Pareto front of the biobjective knapsack problem with one linear objective function (that represents profit) and one nonlinear objective function (that represents risk). The algorithm is composed by two stages. The first stage is using a dynamic programming scheme that constructs a Pareto optimal solution that maximizes the profit objective function, and it is applied in the standard setup of the knapsack problem in which the total weight of the items is bigger than the capacity of the knapsack. In the trivial setup of the problem, in which the total weight of the items is less or equal to the capacity, we apply a greedy algorithm that constructs the remaining solutions that are not constructed in the first stage. We prove mathematically the correctness, the computational complexity and the memory complexity of the proposed algorithm.We demonstrate its execution using comprehensive numerical examples, and we demonstrate its applicability for large-scale instances in the provided experiments results.