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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)824-836
Journal / PublicationEuropean Journal of Operational Research
Volume274
Issue number3
Early online date26 Sep 2018
Publication statusPublished - 1 May 2019

Abstract

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