No-good cuts for general integer variables

Question

Question: Suppose we have an integer program $\min\{c^\top{x}\mid{Ax\leq{b}},x\in\mathbb{Z}_+^n\}$, and suppose that $x^*$ is a feasible solution for this IP (or even that $x^*$ is an extreme point of the convex hull of the feasible region). Is there a method to eliminate $x^*$ (and only $x^*$) from the feasible region, so that if we re-solve the IP, we do not obtain the solution $x^*$?

---

Background: If the integer program contains only binary variables, then we can use a no-good inequality of the form $$ \sum_{i:x^*_i=0}x_i+\sum_{i:x^*_i=1}(1-x_i)\geq1 $$ to eliminate $x^*$ and only $x^*$ from the feasible region. Is there an analogue of this (possibly using multiple inequalities) for general integer variables? I imagine that if $x^*$ is an arbitrary feasible point, the answer is no (unless we use an extended formulation of some kind, or nonlinear inequalities)--one can imagine if $x^*$ is a single point in the middle of the integer lattice, there would be no way to simply punch only that point out of the middle. But if $x^*$ is an extreme point of the convex hull, it seems that it should be possible.

---

One possible solution: One clear solution is to use a binary expansion of the integer variables, and replace all the general integer variables with binary variables. I am wondering if there is a way to do this without a binary expansion (i.e. hopefully in the original space of variables).

Answer 1

This is what I have been using. Assume $\color{darkred}x_i \in \{\color{darkblue}L_i,\dots,\color{darkblue}U_i\}$ and we want: $$ \sum_i |\color{darkred}x_i-\color{darkblue}x_i^*| \ge 1$$ or $$\begin{align} & \color{darkred}z_i \le |\color{darkred}x_i-\color{darkblue}x_i^*| \\ & \sum_i \color{darkred}z_i \ge 1 \end{align}$$ This can be modeled with a binary variable $\color{darkred}\delta_i$ : $$\begin{align} & \color{darkred}z_i\le \color{darkred}x_i-\color{darkblue}x_i^*+\color{darkblue}M_i\cdot\color{darkred}\delta_i \\ & \color{darkred}z_i\le -(\color{darkred}x_i-\color{darkblue}x_i^*)+\color{darkblue}M_i\cdot(1-\color{darkred}\delta_i)\\ & \sum_i \color{darkred}z_i \ge 1\\ &\color{darkred}\delta_i \in \{0,1\} \\ & \color{darkblue}M_i=\color{darkblue}U_i-\color{darkblue}L_i\end{align}$$

A refinement is to consider the two special cases:

• $\color{darkblue}x_i^*=\color{darkblue}L_i$. No need for $\color{darkred}\delta_i$: use $\color{darkred}z_i=\color{darkred}x_i-\color{darkblue}x_i^*$.
• $\color{darkblue}x_i^*=\color{darkblue}U_i$. Again no need for $\color{darkred}\delta_i$: use $\color{darkred}z_i= -(\color{darkred}x_i-\color{darkblue}x_i^*)$.

Answer 2

Here's one way, assuming $L_i \le x_i \le U_i$. Introduce binary variables $y_i$ and $z_i$, with linear constraints \begin{align} \sum_i (y_i+z_i) &\ge 1 \tag1\\ y_i + z_i &\le 1 &\text{for all $i$} \tag2\\ L_i(1-z_i) + (x_i^*+1)z_i \le x_i &\le (x_i^*-1)y_i + U_i(1-y_i) &\text{for all $i$} \tag3\\ \end{align} Constraint $(1)$ forces $y_i \lor z_i$ for some $i$. Constraint $(2)$ forces $\lnot(y_i \land z_i)$ for all $i$. Constraint $(3)$ enforces $y_i = 1 \implies x_i < x_i^*$ and $z_i = 1 \implies x_i > x_i^*$.

Answer 3

If you are willing to entertain an element of risk, and assuming that the feasible region is bounded, you might get away with a single new binary variable $z$. Assume that the feasible region $X$ is bounded, which implies that the number of feasible $x$ is finite. Generate a vector $r\in \mathbb{R}^n$ uniformly over the unit rectangle. Since the feasible region is finite, $\mathrm{Pr}(r^\prime x = r^\prime x^*)=0$ for any $x^*\neq x\in X$. So adding the constraint $r^\prime x \neq r^\prime x^*$ gets rid of $x^*$ while (with probability 1) not eliminating any other feasible solution. This is true even if $x^*$ is in the interior of the convex hull of $X$.

The catch is that $\neq$ constraints are not allowed. So we introduce a single binary variable $z$, a tolerance parameter $\epsilon > 0$ and an upper bound $M$ on $\left( \vert r^\prime x - r^\prime x^*\vert + \epsilon \right)$ for all $x\in X$ and add the constraints $$r^\prime x^* + \epsilon -M(1-z) \le r^\prime x \le r^\prime x^* -\epsilon + Mz.$$The probability of excluding a feasible point is no longer zero, but it should be small (assuming $\epsilon$ is small). So I would call this approach "low risk" as opposed to "risk free".