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$
1
$\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, privacy policy and cookie policy

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