Concave Mixed-Integer Quadratic Programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ε-approximate solution to a Concave Mixed-Integer Quadratic Programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ε, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P = NP.
Citation
Submitted manuscript