AN IMPROVED CONVEX 0-1 QUADRATIC PROGRAM REFORMULATION FOR CHANCE-CONSTRAINED QUADRATIC KNAPSACK PROBLEMS

We consider a chance-constrained quadratic knapsack problem (CQKP) where each item has a random size that is finitely distributed. We present a new convex 0-1 quadratic program reformulation for CQKP. This new reformulation improves the existing reformulation for general 0-1 quadratic program based on diagonal perturbation in the sense that the continuous relaxation of the new reformulation is tighter than or at least as tight as that of the existing reformulation. The improved reformulation is derived from a general matrix decomposition of the objective function and piecewise linearization of 0-1 variables. We show that the optimal parameters in the improved reformulation can be obtained by solving an SDP problem. Extension to k-item probabilistic quadratic knapsack problems is also discussed. Preliminary comparison results are reported to demonstrate the effectiveness of the improved reformulation.