Home | Legals | Sitemap | KIT

Solving Multiple and Multidimensional Knapsack problems in Empirical Orthogonal Function Space

Solving Multiple and Multidimensional Knapsack problems in Empirical Orthogonal Function Space

Prof. T. Setzer 

Existing approaches to solve larger packing problems typically fix variables and define efficiency criteria relating item profits and weights to reduce problem complexity. We work on empirical-orthogonal constraint generation (EOCG) to transform a multidimensional knapsack problem (MKP) and other types of packing problems into a lower-dimensional representation. With EOCG we transform the constraint space itself with the aim of reformulating the problem with as few constraint dimensions as necessary. The intuition is to not rely on original dimensions but to determine novel dimensions.

In a nutshell, we determine candidates for the direction of the d+1th constraint dimension, orthogonal to the d-dimensions space already considered, that form a regular simplex of the residual space not yet considered, where the capacities in a dimension depend linearly on the slacks on a previous dimension. From the candidates, we choose the one with the highest dual with the optimal item set in the $d$-dimension constraint space. The algorithm terminates with the optimal solutions when no capacity violations are observed in a dimension, which then bounds the intrinsic'' problem dimensionality.

We evaluate EOCG through computational studies on MKP benchmark problems from the literature and self-generated problems.

One finding is that the true dimensionality of problem instances is typically lower than the original problem dimensionality even though a pre-solving engine cannot reduce a problem's size. A second finding is that for high-dimensional problems, EOCG improves the solutions found with the original formulation, and derives the best-known objective values for most benchmark instances with a lower-dimensional problem formulation.