 |
Constraint Programming for Strictly Convex Integer Quadratic Programs
Members
J. Christopher Beck
Wen-Yang Ku
|
Project description
Inspired by the geometric reasoning exploited in discrete ellipsoid-based search (DEBS) from the communications literature, we develop a constraint programming (CP) approach to solve problems with strictly convex quadratic constraints. Such constraints appear in numerous applications such as modelling the ground-to-satellite distance in global positioning systems and evaluating the efficiency of a schedule with respect to quadratic objective functions. We strengthen the key aspects of the DEBS approach and implement them as combination of a global constraint and variable/value ordering heuristics in IBM ILOG CP Optimizer. Experiments on a variety of benchmark instances show significant improvement compared to the default settings and state-of-the-art performance compared to competing technologies of mixed integer programming (MIP), semi-definite programming (SDP), and mixed integer nonlinear programming (MINLP).
Start date
January 2015
Funding
University of Toronto Fellowship
TIDEL Research Assistantship
Publications
- Ku, W.Y. & Beck, J.C., "Constraint Programming for Strictly Convex Integer Quadratically-Constrained Problems", Proceedings of the Twenty-Second International Conference on Principles and Practice of Constraint Programming, (CP2016), 316-332, 2016.
|
