CORAL Seminar: Renata Mansini, University of Brescia, Italy

Title: New results on the Multidimensional Knapsack Problem

2013.09.17 | Bodil Westermann Krog

Date Thu 21 Nov
Time 14:30 16:00
Location Fuglesangs Allé 4, 8210 Aarhus V, building 2628(M), room 323

Speaker: Renata Mansini, Department of Information Engineering, University of Brescia, Italy, rmansini@ing.unibs.it

Title: New results on the Multidimensional Knapsack Problem

Abstract: The Multidimensional Knapsack Problem (MKP) is a well-known strongly NP-hard problem and one of the most challenging problems in the class of the knapsack problems. In the last years it has been a favorite playground for meta-heuristics while very few contributions have appeared on exact methods. In this talk we will outline some new directions of research on this problem and present a new exact approach called CORAL (for CORe ALgorithm). CORAL can be seen as a continuous lower bound improvement procedure that works through the optimal solution of subproblems limited to subsets of variables. Each subproblem is optimally solved through a two-steps procedure. In the first step the set of items is reduced through a recursive variables fixing process up to a predefined size. Then, in the second step, the remaining subproblem (Restricted Core problem) is optimally solved. The solution space is split into subspaces, each containing solutions of a given cardinality. Each subspace is then explored with a branch-and-bound algorithm. In all the tested instances, the proposed method has shown to be, on average, more efficient with respect to state of art algorithms. We have been able to improve the best known solutions for some of the largest and most difficult instances of the OR-LIBRARY data set (Chu and Beasley 1998).

Key Words: Multidimensional Knapsack Problem; exact algorithm; reduced costs;
recursive variables fixing; cardinality constraint

Organizer: Sanne Wøhlk

CORAL seminars