# How to exclude all points adjacent to a given point from the feasible region of IP

Consider a basic integer program such as:

\begin{align} \min_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x_i \in \{-100,\ldots,100\} \end{align}

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a feasible point $y \in \mathbb{Z}^n \cap [-100,100]^n$ with the property that all points adjacent to $y$ cannot be optimal. In other words, given $y$, all points in the set:

$$\mathcal{A}(y) = \Big\{ z \in \mathbb{Z}^d ~\big|~ z_i = y_i \pm 1 \Big\}$$

could be excluded from the feasible region of the IP.

I am wondering if there is an elegant way to formulate constraints that will exclude all points that adjacent to $y$ from the feasible region.

• I doubt that's the definition of $A(y)$ you meant. Maybe you meant $|z_i-y_i| \le 1$? (You need to allow the possibility that $z_i=y_i$ for some of the indices $i$.)
– D.W.
Aug 1, 2015 at 6:39
• I'm having trouble understanding your question. What do you mean by the last sentence? You've already given us the constraints. We're allowed to add new constraints? Are we allowed to add new variables? Is $y$ given to us? What is the motivation/context/purpose of doing this?
– D.W.
Aug 1, 2015 at 6:41
• @D.W. Thanks for the follow up questions! In terms of motivation, I have a procedure that I can use that will return a "locally optimal" solution $y$. The purpose of removing the adjacent points in $\mathcal{A}(y)$ is to reduce the size of the feasible region and improve the lower bound to the objective value that will be produced by a continuous relaxation. I understand that it may require new variables / constraints, but I was looking for a way to do it using as few variables / constraints as possible. Aug 1, 2015 at 19:29
• @D.W. Actually, you could also remove $y$ from the feasible region. I will reword. When I first wrote the question, I thought that it wasn't a good idea since $y$ might be the optimal solution so the IP would return a different result. That said, we could solve the IP without $\mathcal{A}(y)$ and $y$. In this case, we would know that the solution we obtain is optimal iff it attains an objective that is less than or equal to $c^Ty$. Aug 1, 2015 at 19:34
• I'm looking again at this question, since you linked to it in your latest question. It's still not clear to me what points you want to remove from consideration. Do you want to remove $\{z : |z_i - y_i| = 1\}$? (doesn't include $y$ in the set) $\{z : |z_i - y_i| \le 1\}$? (does include $y$) Something else? Currently what you wrote is equivalent to the former, but I'm suspicious that's not actually what you want. Also, the question doesn't state whether it's allowed to add new variables.
– D.W.
Jan 8, 2016 at 23:49

## 1 Answer

You can't eliminate all points in $A(y) \setminus \{y\}$ without also eliminating $y$, as the conjunction of a bunch of linear inequalities always gives a convex region, and $A(y) \setminus \{y\}$ is non-convex.

Here I am assuming we're not allowed to introduce new variables. If we're allowed to introduce new variables, there are many uninteresting ways to achieve it, by taking advantage of the fact that with integer variables you can express any logical predicate you like; however, it seems unlikely that this will be useful for anything in practice.