Multiple knapsack problem with inter-related items and its applications to real world problems

Abstract

Motivated by a real world application, we study a variant of the classic knapsack problem, which we call the Multiple Knapsack Problem with Inter-related Items (MKPIR). We are given a set of items and a set of knapsacks of limited capacity. For each item, a set of knapsacks that can hold that item is specified. In addition, binary relationships may exist between the items. These relationships affect the profit of having that item in the knapsack in consideration. In this thesis, we adopted a few heuristics and test them on the venue assignment problem, instance of MKPIR, using actual data and randomly generated test instances.