size of solution

Mixed-integer Quadratic Programming is in NP

  • Alberto Del Pia
  • Santanu S. Dey
  • Marco Molinaro
    • Categories Integer Programming Tags , ,

    Mixed-integer quadratic programming (MIQP) is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing … Read more