Lifting of probabilistic cover inequalities

Abstract

We consider a chance-constrained binary knapsack problem where weights of items are independent and normally distributed. Probabilistic cover inequalities can be defined for the problem. The lifting problem for probabilistic cover inequalities is NP-hard. We propose a polynomial time approximate lifting method for probabilistic cover inequalities based on the robust optimization approach. We present computational experiments on multidimensional chance-constrained knapsack problems. The results show that our lifting method reduces the computation time substantially.