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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)824-836
Journal / PublicationEuropean Journal of Operational Research
Issue number3
Online published26 Sept 2018
Publication statusPublished - 1 May 2019


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.

Research Area(s)

  • Integer programming, Mixed integer quadratic programming, On–off constraint, Quadratic convex reformulation, Semidefinite program