New perspectives on multi-objective knapsack problems

En savoir plus sur le livre

Knapsack problems are highly relevant in real-world applications, particularly in financial and industrial management, where decision-making often involves multiple criteria, such as risk versus return or economic versus ecological considerations. This work explores multi-objective knapsack problems from three perspectives. First, it examines the interrelations between supported points, the weight space, and concepts from combinatorial geometry, leading to the formulation of efficient algorithms for computing the set of supported points in multi-objective unconstrained combinatorial optimization and knapsack problems with both positive and negative coefficients. This set provides a meaningful representation for such problems. Second, it analyzes the trade-off between constraint satisfaction and objective value by transforming "soft" constraints of multi-dimensional knapsack problems into objective functions. An efficient algorithm is presented to compute the optimal solution and alternative efficient solutions that are "close" to it. Lastly, the introduction of rectangular knapsack problems as a specific case of quadratic knapsack problems offers a new concept for closed formulation in hypervolume maximization, where a representative solution of a bi-objective knapsack problem corresponds to the optimal solution of an associated rectangular knapsack problem.