Cheap and Secure Web Hosting Provider : See Now

[Solved]: Formulating a constraint to exclude a single point from the feasible region of an IP?

, , No Comments
Problem Detail: 

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

Asked By : Berk U.

Answered By : Erwin Kalvelagen

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51645

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback