Concave Quadratic Cuts for Mixed-Integer Quadratic Problems
arXiv:1510.06421
Abstract
The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice , and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.
arXiv comment24 pages, 1 figure
References in corpus (6)
- Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model
- Supersparse Linear Integer Models for Optimized Medical Scoring Systems
- Designing Unimodular Codes via Quadratic Optimization is not Always Hard
- Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems
- How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic
- A Frank-Wolfe Based Branch-and-Bound Algorithm for Mean-Risk Optimization