Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem (Q840573)

Summary: In this paper, we propose three versions of an algorithm for approximately solving large-scale \textit{multiple-choice multi-dimensional knapsack problems} (MMKP). First, an adaptation of the local branching is proposed. Second, a hybrid solution procedure is presented that is based on two complementary solution procedures: a local branching which cooperates with a column generation solution procedure. Third and last, an augmented algorithm of the last hybrid algorithm is developed. It can also be viewed as a special truncated branch-and-bound in which the first hybrid algorithm is applied to a subset of elite nodes generated according to some variables/constraint branchings. The proposed methods are analysed computationally on a set of instances from the literature and compared to the results provided by other algorithms therein. Encouraging results have been obtained.