0
$\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 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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$.) $\endgroup$
    – D.W. ♦
    Commented Aug 1, 2015 at 6:39
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented Aug 1, 2015 at 6:41
  • $\begingroup$ @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. $\endgroup$
    – Berk U.
    Commented Aug 1, 2015 at 19:29
  • $\begingroup$ @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$. $\endgroup$
    – Berk U.
    Commented Aug 1, 2015 at 19:34
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jan 8, 2016 at 23:49

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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