A new variable reduction technique for convex integer quadratic programs

Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems.