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.
How to exclude all points adjacent to a given point from the feasible region of IP
optimization;discrete mathematics;integer programming
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.