New upper bounds and exact methods for the knapsack sharing problem

- A new upper bound is proposed for the knapsack sharing problem.
- A new dichotomous search-based exact algorithm is proposed.
- The new algorithm outperforms a most recent exact algorithm of the literature and the Cplex solver V 12.

In this paper, we study the knapsack sharing problem (KSP), which is a variant of the well-known NP-Hard knapsack problem. We investigate the use of a dichotomous search-based exact method for solving the KSP. Such a method is based on decomposing the original problem into a series of minimizing and maximizing knapsack problems, where each of them is embedded into a dichotomous search bounded by both lower and upper bounds. Throughout the interval search, we introduce new upper bounds and incremental valid lower bounds. One of these upper bounds can be viewed as an extended of Dantzig upper bound whereas a series of valid lower bounds are obtained when solving a subset of knapsack problems. Finally, the proposed algorithm is evaluated on a set of problem instances of the literature and other new harder ones. The provided results are compared to those reached by the Cplex solver and a more recent exact algorithm of the literature. The computational part shows the dominance of the new exact method.