A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem

摘要: Abstract The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization with number of important applications. In this paper, we present “reduce and solve” heuristic approach which combines reduction techniques an Integer Linear Programming (ILP) solver (CPLEX). key ingredient the proposed set group fixing variable rules. These rules rely mainly on information from linear relaxation given aim to generate reduced critical subproblem be solved by ILP solver. Additional strategies are used explore space problems. Extensive experimental studies over two sets 37 MMKP benchmark instances in literature show that our competes favorably most recent state-of-the-art algorithms. particular, for 27 conventional benchmarks, finds improved best lower bound 11 as by-product improves all previous upper bounds. For 10 additional irregular structures, method 7 known results.