2
$\begingroup$

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 point $y \in \mathbb{Z}^n \cap [-100,100]^n$ that I would like to exclude from the feasible region.

I am wondering if there is an elegant way to do this without introducing new variables to the formulation? If there is no way to exclude $y$ from the feasible region without adding new variables to the formulation, then is an approach that allows me to do this by adding the fewest possible variables?

I should add that this question is loosely related to a different question that I posted here a few months ago (though there was no concrete answer given to that one either).

$\endgroup$
2
$\begingroup$

You need to add an integer cut of the form: $$ \sum_i |x_i - y_i| \ge 1 $$ where $y_i$ is your point your want to exclude.

We can rewrite this as: $$ \begin{align} &\sum_i z_i \ge 1 \\ &z_i \le |x_i - y_i| \end{align} $$ The last inequality is identical to $z_i \le \max\{x_i-y_i, -(x_i-y_i)\}$. This again can be implemented using additional binary variables: $$ \begin{align} &z_i\le x_i-y_i+M_i\delta_i \\ &z_i\le -(x_i-y_i)+M_i(1-\delta_i) \\ &\delta_i \in \{0,1\} \\ &M_i = U_i - L_i = 200 \end{align} $$ There are two special cases we can handle more efficiently. If $y_i=L_i=-100$ then we can write $z_i = x_i - y_i$. If $y_i=U_i=100$ then we can write $z_i=-(x_i-y_i)$.

$\endgroup$
  • $\begingroup$ Thanks - this is exactly what I was looking for! To be clear, to exclude a single point in $n$ dimensions, you need to add $2n$ additional variables $z_i$ and $\delta_i$ as well as $2n+1$ constraints. Is that right? $\endgroup$ – Berk U. Jan 29 '16 at 17:40
  • $\begingroup$ This looks to be correct. $\endgroup$ – Erwin Kalvelagen Jan 29 '16 at 20:39
1
$\begingroup$

Here's one possible approach you could try, though I don't know if it will be optimal. One heuristic is to pick a random vector $d$, and then look for solutions where either $d^T x < d^T y$ or $d^T x > d^T y$. In other words, we pick a random vector $d$, and then we solve the two integer programs

  • $\min c^T x$ such that $Ax \le b$, $d^T x < d^T y$ (note that $d^T y$ is a known constant), $|x_i| \le 100$.

  • $\min c^T x$ such that $Ax \le b$, $d^T x > d^T y$, $|x_i| \le 100$.

and then check to see whether either has a solution.

For instance, you might choose $d$ randomly from $\{-1,0,1\}^n$, or even from $\{-100,\dots,100\}^n$.

Warning: This is not a principled solution: it's possible that all other optimal solutions to the integer program just happen to satisfy $d^T x = d^T y$. The idea is that, if you choose $d$ randomly, this is unlikely to hold: it would require that $d^T (x-y)=0$, and for any fixed $x,y$ with $x\ne y$, the probability of that is relatively small. However, this is not an absolute guarantee, and it's certainly possible that you could get unlucky and miss out on optimal solution in this way.

There are some ways to reduce the probability of missing an optimal solution, but you can't reduce it to zero with this approach. The domain from which you choose $d$ affects the probability: the larger the range of possible values for each coordinate of $d$, the smaller the probability will be. Also, if you wished, you could repeat this procedure multiple times to reduce the likelihood of missing out on an optimal solution, but I don't know if that tradeoff will be worth it in a practical application.


[ Equivalently, instead of solving two integer programs, you can solve add a new variable and solve just one integer program. In particular, introduce a new zero-or-one variable $z$ and add the constraints $0 \le z \le 1$, $d^T x < d^T y + Cz$, $d^T x > d^T y - C(1-z)$, where $C$ is a very large constant, say $C > d^T y + 100 ||d||_1$. This is equivalent to solving those two integer programs, though I don't know that there's any particular advantage to this instead of solving two separate integer programs. ]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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