Nonlinear 0-1 knapsack problem with capacity selection

Abstract

We study a nonlinear 0-1 knapsack problem with capacity selection decision, as it arises as a part of facility location/service system design problems with congestion. The capacity selection decision gives rise to a non-convex objective function. We present two cutting plane based solution approaches: one based on Generalized Benders decomposition based, and the other based on a reformulation of the problem using additional auxiliary variables, followed by outer linearization of a resulting simple concave function in the constraint.