  


Mixedinteger Quadratic Programming is in NP
Alberto Del Pia(alberto.delpiagmail.com) Abstract: Mixedinteger 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 mixedinteger quadratic programming is in NP, thereby showing that it is NPcomplete. This is established by showing that if the decision version of mixedinteger 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 and integer linear programming is in NP. Keywords: Mixedinteger Quadratic Programming, Complexity, Size of Solution Category 1: Integer Programming Citation: Download: [PDF] Entry Submitted: 07/17/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  