On linear conic relaxation of discrete quadratic programs. (3rd July 2016)

• Record Type: Journal Article
• Authors: Nie, Tiantian; Fang, Shu-Cherng; Deng, Zhibin; Lavery, John E.
• Is Part Of: Optimization methods and software. Volume 31:Number 4(2016)
• Page Start: 737
• Page End: 754
• Publication Date: 2016-07-03
• Subjects: discrete quadratic program -- linear conic relaxation -- RLT method; 90C-10 -- 90C-20 -- 90C-26; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1134528
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : A special reformulation-linearization technique based linear conic relaxation is proposed for discrete quadratic programming (DQP). We show that the proposed relaxation is tighter than the traditional positive semidefinite programming relaxation. More importantly, when the proposed relaxation problem has an optimal solution with rank one or two, optimal solutions to the original DQP problem can be explicitly generated. This rank-two property is further extended to binary quadratic optimization problems and linearly constrained DQP problems. Numerical results indicate that the proposed relaxation is capable of providing high quality and robust lower bounds for DQP.