Supermodular covering knapsack polytope

The supermodular covering knapsack set is the discrete upper level set of a non‐decreasing supermodular function. Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. In a recent paper Atamtürk and Narayanan (2009) study the lower level set of a non‐decreasing submodular function. In this complementary paper we describe pack inequalities for the supermodular covering knapsack set and investigate their separation, extensions and lifting. We give sequence‐independent upper bounds and lower bounds on the lifting coefficients. Furthermore, we present a computational study on using the polyhedral results derived for solving 0–1 optimization problems over conic quadratic constraints with a branch‐and‐cut algorithm.