2
$\begingroup$

Let $x$ be an integer such that $x \in [ - 10,10]$ and $b$ a binary variable. Apply integer programming to express $b = 1 \leftrightarrow x \ge3$

My work:

\begin{equation} \begin{cases} \text{if}\,\,\,\,\ b = 1, & \text{then}\,\,\,\,\,\,\ x \ge3 \\ \text{if}\,\,\,\,\ x \ge3, & \text{then}\,\,\,\,\,\,\ b = 1 \end{cases} \end{equation}

I got the following encoding $$3 + {M_1}(1 - b) \le x \le 2 + {M_2}b$$where $${M_1} \le- 13{\text{ and }}{M_2} \ge8$$

Checking:

Case: $b = 0$ $$3 + {M_1} \le x \le 2$$For ${M_1} \le - 13$, we have $x = - 10, - 9, \ldots ,2$

Case: $b = 1$ $$3 \le x \le 2 + {M_2}$$ For ${M_2} \ge 8$, we have $x = 3, 4, \ldots ,10$

Thus, by choosing $b = \{ 0,1\} $ we can force $x$ to take any value from its domain.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Let $x \in [-10,10] \cap \mathbb Z$ and $y \in \{0,1\}$. Suppose that

$$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$

To ensure that $y \neq 0$ when $x \geq 3$, use

$$y \geq \frac{x-2}{8}$$

To ensure that $y \neq 1$ when $x \leq 2$, use

$$y \leq \frac{x+10}{13}$$

Pictorially,

enter image description here

The trivial inequality constraints are $-10 \leq x \leq 10$ and $0 \leq y \leq 1$. Lastly, the integrality constraints $x, y \in \mathbb Z$ should not be forgotten.

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