An Exact Solution Search for the Max-Min Multiple Knapsack Problem

In this paper, we propose to solve the max-min multiple knapsack problem by using an exact solution search. An instance of the problem is defined by a set of n items to be packed into m knapsacks as to maximize the minimum of the knapsacks' profits. The proposed method uses a series of interval searches, where each interval is bounded with a target value (considered as a lower bound) and an estimated upper bound. The target lower bound is computed by applying some aggressive fixation of some items to optimality whereas the upper bound is computed by using a surrogate relaxation. The performance of the proposed method is evaluated on a set of instances containing a variety of sizes. Computational results showed the superiority of the proposed method when comparing its provided results to those obtained by the Cplex solver and one of the best exact method available in the literature.