Department of Industrial Engineering & Decision Analytics [Joint IEDA/MATH] seminar - A Polynomial-Time Algorithm for Mixed-Integer Quadratic Programming in Fixed Dimensions  

We give a deterministic polynomial-time algorithm for integer quadratic programming in every fixed dimension: it minimizes an arbitrary rational quadratic exactly over the integer points of a rational polyhedron, or certifies infeasibility or integer unboundedness. The core is a sign test that decides whether dTQd≥ 0 for every integer point d of a bounded symmetric rational polytope. It proceeds through a dyadic sequence of scaled copies of the polytope, starting at a scale at which the origin is its only integer point, converting nonnegativity at each scale into integer supporting inequalities on a constant-size cover of the next, and minimizing exactly by cuts through integer points of constant halfspace depth. Dyadic grouping of the constraint slacks handles general linear constraints, and an integer unboundedness test and an optimizer bound handle unbounded polyhedra. The running time is polynomial in the binary input length, with an exponent depending on the dimension.