Return to Question

I have the quadratic integer program over $\mathbb{Z}^n$

$\displaystyle\min_{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$

$\displaystyle\min_{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!

I have the quadratic integer program over $\mathbb{Z}^n$

$\displaystyle\min_{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$

$\displaystyle\min_{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!

I have the quadratic integer program over $\mathbb{Z}^n$

$\displaystyle\min_{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\}$. 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$

$\displaystyle\min_{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!

I have the quadratic integer program over $\mathbb{Z}^n$

$\displaystyle\min_{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$

$\displaystyle\min_{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!