New perspectives on multi-objective knapsack problems

Knapsack problems have a high relevance in real-world applications. They are applicable, for example, in financial and industrial management. Many decision problems have to take two or more criteria into account, for example, risk versus return or economical versus ecological criteria. We consider multi-objective knapsack problems from three perspectives. We ... (1) ... present interrelations between supported points, the weight space and concepts from combinatorial geometry. These insights are used to formulate efficient algorithms to compute the set of supported points of multi-objective unconstrained combinatorial optimization problems and of multi-objective knapsack problems with positive and negative coefficients. The set of supported points provides a meaningful representation for multi-objective combinatorial optimization problems. (2) ... analyze the trade-off between constraint satisfaction and objective value by transforming „soft“ constraints of multi-dimensional knapsack problems into objective functions. For the resulting multi-objective knapsack problem we present an efficient algorithm that computes the optimal solution and alternative efficient solutions that are „close“ to it. (3) ... introduce rectangular knapsack problems as a special case of quadratic knapsack problems. Rectangular knapsack problems constitute a completely new concept for a closed formulation for hypervolume maximization. A representative solution of a bi-objective knapsack problem is given by the optimal solution of an associated rectangular knapsack problem.