I have the quadratic integer program over $mathbb{Z}^n$
$displaystylemin_{z in mathbb{Z}^n} Phi (z) = frac{1}{2} z^T Q z - r^T z + s$
subject to $G z = h$, and $z_i in {0,1,2,dots, b_i}$ for all $i in {1,2,dots,n}$, where $Q$ is symmetric positive-definite. Moreover, $G, h$ are integer-valued and, thus, I suppose that ${z in mathbb{Z}^n : G z = h}$ defines a sublattice of $mathbb{Z}^n$.
Let us suppose we solve the relaxed quadratic program over $mathbb{R}^n$
$displaystylemin_{x in mathbb{R}^n} Psi (x) = frac{1}{2} x^T Q x - r^T x + s$
subject to $G x = h$, and $0 leq x_i leq b_i$ for all $i in {1,2,dots,n}$. Let $x_{opt} in mathbb{R}^n$ be the minimizer of $Psi$. We can define an $n$-cube (in $mathbb{Z}^n$) containing $x_{opt}$ by taking the floor/ceil of each component of $x_{opt}$. We intersect this $n$-cube with the integer sublattice defined by $G z = h$, and evaluate $Phi$ at all points of this intersection. Let $z^{ast}$ be the point in such intersection that minimizes $Phi$. Let $z_{opt}$ be the minimizer of the original quadratic integer program. Can we say that $z_{opt} = z^*$? I know nothing of integer programming, so I preemptively apologize if my question is silly / elementary...
In other words, can one solve a quadratic integer program by solving a relaxed quadratic real program, and then searching in the neighborhood of the real solution? This seems to work for $n = 1$ and $n = 2$... but it also seems too good to be true in general. If in general $z_{opt} neq z^{ast}$, can we (at least) quantify how sub-optimal $z^{ast}$ is?
Any feedback will be most welcome!
No comments:
Post a Comment