On the gap between the quadratic integer programming problem and its semidefinite relaxation |
| |
Authors: | U Malik IM Jaimoukha GD Halikias SK Gungah |
| |
Institution: | (1) Control and Power Group, Dept. Electrical and Electronic Eng, Imperial College, London, SW7–2BT, UK;(2) School of Engineering and Mathematical Sciences, City University, Northampton Square, London, EC1V–0HB, UK |
| |
Abstract: | Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap We establish the uniqueness of the SDR solution and prove that if and only if γr:=n−1max{xTVVTx:x ∈ {-1, 1}n}=1 where V is an orthogonal matrix whose columns span the (r–dimensional) null space of D−Q and where D is the unique SDR solution. We also give a test for establishing whether that involves 2r−1 function evaluations. In the case that γr<1 we derive an upper bound on γ which is tighter than Thus we show that `breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the
cost function matrix equal to the dimension of the null space of D−Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r. |
| |
Keywords: | Quadratic integer programming Semidefinite relaxation Linear matrix inequalities Zonotopes Hyperplane arrangements |
本文献已被 SpringerLink 等数据库收录! |
|