Mixed-integer quadratic programming is in NP

• 成果类型: Article
• 署名作者: Del Pia, Alberto; Dey, Santanu S.; Molinaro, Marco
• 署名单位: University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Pontificia Universidade Catolica do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1036-0
• 发表日期: 2017
• 页码: 225-240
• 关键词: Complexity

摘要

Mixed-integer quadratic programming 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 that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generalizes and unifies classical results that quadratic programming is in NP (Vavasis in Inf Process Lett 36(2):73-77 [17]) and integer linear programming is in NP (Borosh and Treybig in Proc Am Math Soc 55:299-304 [1], von zur Gathen and Sieveking in Proc Am Math Soc 72:155-158 [18], Kannan and Monma in Lecture Notes in Economics and Mathematical Systems, vol. 157, pp. 161-172. Springer [9], Papadimitriou in J Assoc Comput Mach 28:765-768 [15]).