An exact algorithm for the Knapsack problem with setup (Q840596)

Summary: In this paper, we study a \(0-1\) Knapsack problem with setup (KPS). One set of \(0-1\) variables represents a family setup and serves as an upper bound (UB) on another set of \(0-1\) variables representing production of a job in a family. We present a branch-and-bound algorithm to find an optimal solution to KPS. The algorithm uses a two-stage branching strategy and chooses the next candidate problem to be explored in a non-traditional way. We verify the efficiency of the algorithm through computational testing. This is the first time that an exact algorithm is applied to a KPS with 10,000 integer variables. Computational experiments show that the algorithm is especially effective when objective and constraint coefficients are uncorrelated.