9
$\begingroup$

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).

$\endgroup$
2
  • 1
    $\begingroup$ citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Kuifje
    Apr 24, 2021 at 21:33
  • $\begingroup$ Please remember that for typical MIP solvers noone can guarantee that the optimal IP solution that was found is an extreme point of the convex hull of the feasible solutions. So it is unclear whether such an algorithm will help you at all. $\endgroup$
    – T_O
    Apr 25, 2021 at 11:53

3 Answers 3

6
$\begingroup$

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^*)$.
$\endgroup$
8
$\begingroup$

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^*$.

$\endgroup$
2
  • $\begingroup$ should the $y_i$ and $z_i$ have an index k (distinct solution k ? ) $\endgroup$ Jul 25, 2022 at 22:07
  • 1
    $\begingroup$ Yes, this formulation cuts off only one solution $x*$, so include an additional index (like $y_{ik}$ and $z_{ik}$) if you want to cut off multiple solutions. $\endgroup$
    – RobPratt
    Jul 25, 2022 at 22:11
6
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.