Quadratic convex reformulation for quadratic programming with linear on–off constraints

In production planning and resource allocation problems, we often encounter a situation where a constraint can be relaxed or removed if new resources are added. Such constraints are termed on–off constraints. We study the quadratic programming problem with such on–off constraints, which is in general NP-hard. As the problem size grows, branch-and-bound algorithms for the standard formulation of this problem often require a lot of computing time because the lower bound from the continuous relaxation is in general quite loose. We generalize the quadratic convex reformulation (QCR) approach in the literature to derive a new reformulation that can be solved by standard mixed-integer quadratic programming (MIQP) solvers with less computing time when the problem size becomes large. While the conventional QCR approach utilizes a quadratic function that vanishes on the entire feasible region, the approach proposed in our paper utilizes a quadratic function that only vanishes on the set of optimal solutions. We prove that the continuous relaxation of our new reformulation is at least as tight as that of the best reformulation in the literature. Our computational tests verify the effectiveness of our new approach.