Casting to boolean in integer linear programming

Question

I have variables $x \in \{0,1,\dots,5\}$ and $y \in \{0,1\},ドル where

$$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$

My problem is to maximize $y$. How can I use linear constraints for this?

I tried certain cases like Cast to boolean, for integer linear programming but that won't work if the problem is to maximize $y$.

• Eugene: What about $y \leq 5-x$?
• Yuval Filmus: @Eugene This ensures that $y = 0$ if $x = 5,ドル but doesn't ensure that $y = 1$ otherwise.
• Eugene: @Yuval Filmus Indeed, it does not alone. But with objective maximize $y$ mentioned by OP and $y$ - binary, it should.

Answer 1

Add the following two constraints: $$ y \leq 5-x \\ y \geq 1-x/5 $$ If $x = 5,ドル then these constraints state that $y \leq 0$ and $y \geq 0,ドル hence $y = 0$. If $x \leq 4,ドル then 5ドル-x \geq 1,ドル and so the first constraint doesn't impose any constraint on $y$. On the other hand, 1ドル-x/5 > 0,ドル forcing $y = 1$; and this assignment satisfies the constraint since $x \geq 0$ implies 1ドル-x/5 \leq 1$.

Answer 2

Let $f : \{0,1,\dots,5\} \to \{0,1\}$ be defined by

$$f (x) := \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$

Let $ y = f (x)$. We would like to maximize $y$. Note that the preimage of 1ドル$ is

$$f^{-1} (1) = \{0,1,2,3,4\}$$

Wherever $y$ appears, just make $y = 1$ and then append the constraints 0ドル \leq x$ and $x \leq 4,ドル where $x \in \mathbb N$. Instead of an optimization problem, we have a decision problem that can be solved via integer programming, e.g.,

$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & \color{grey}{\text{(linear constraints on } x \text{)}}\\ & 0 \leq x \leq 4\\ & x \in \mathbb N\end{array}$$