We construct an algorithm for the accurate solution of mixed integer convex quadratic programming, which is the problem of minimizing a convex quadratic function over mixed integer points in a polyhedron. Our algorithm is fixed parameter tractable with parameter the number of integer variables. In particular, when the number of integer variables is fixed, the running time of our algorithm is bounded by a polynomial of the size of the problem. To design our algorithm, we prove a number of fundamental structural and algorithmic results for mixed integer linear and quadratic programming.

翻译：暂无翻译