Robust optimization approach for a chance-constrained binary knapsack problem (Q291067)

The authors consider the binary knapsack problem under the assumption that the weights of items are independent random variables with normal distributions and standard deviations. The problem is to maximize the total profit in such a way that the probability of satisfying the knapsack constraints exceeds a given threshold. The authors describe feasible solutions by linear constraints with the coefficient matrix represented by an ellipsoidal uncertainty set with a quadratic loss function. Using piecewise linear functions they approximate the ellipsoidal uncertainty set by a bounded convex polyhedron. As a result, the problem is reduced to a robust binary knapsack problem with a polyhedral uncertainty set. The authors prove the effectiveness of the proposed approximation and estimate the probability of satisfying the knapsack constraints. Finally, the robust binary knapsack problem with a polyhedral uncertainty set is reduced to a number of ordinary knapsack problems that can be solved in pseudo-polynomial time. The authors present the results of computational tests to demonstrate the effectiveness of the proposed approach.