Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach
Publication in refereed journal

Times Cited
Web of Science19WOS source URL (as at 01/03/2021) Click here for the latest count
Altmetrics Information

Other information
AbstractWe consider in this paper quadratic programming problems with cardinality and minimum threshold constraints that arise naturally in various real-world applications such as portfolio selection and subset selection in regression. This class of problems can be formulated as mixed-integer 0-1 quadratic programs. We propose a new semidefinite program (SDP) approach for computing the "best" diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation of the problem. We also give an alternative way of deriving the perspective reformulation by applying a special Lagrangian decomposition scheme to the diagonal decomposition of the problem. This derivation can be viewed as a "dual" method to the convexification method employing the perspective function on semicontinuous variables. Computational results show that the proposed SDP approach can be advantageous for improving the performance of mixed-integer quadratic programming solvers when applied to the perspective reformulations of the problem.
All Author(s) ListZheng XJ, Sun XL, Li D
Journal nameINFORMS Journal on Computing
Volume Number26
Issue Number4
Pages690 - 703
LanguagesEnglish-United Kingdom
Keywordsdiagonal decomposition; Lagrangian decomposition; perspective reformulation; quadratic programming with semicontinuous variables and cardinality constraint; semidefinite program
Web of Science Subject CategoriesComputer Science; Computer Science, Interdisciplinary Applications; Operations Research & Management Science

Last updated on 2021-02-03 at 00:50