Ulrich Pferschy We study the multidimensional knapsack problem, present some theoretical and empirical results about its structure, and evaluate different Integer Linear Programming (ILP) based, metaheuristic, and collaborative approaches for it. We start by considering the distances between optimal solutions to the LP-relaxation and the original problem and then introduce a new core concept for the MKP, … Read more
For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges … Read more
We extend the classical 0-1 knapsack problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the knapsack. These constraints are represented by edges of a conflict graph whose vertices correspond to the items of the knapsack problem. Similar conditions were treated in the literature for bin … Read more