# Casting to boolean in integer linear programming

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

• What about $y \leq 5-x$? – Eugene Mar 30 '17 at 8:30
• @Eugene This ensures that $y = 0$ if $x = 5$, but doesn't ensure that $y = 1$ otherwise. – Yuval Filmus Mar 30 '17 at 10:40
• @Yuval Filmus Indeed, it does not alone. But with objective maximize $y$ mentioned by OP and $y$ - binary, it should. – Eugene Mar 30 '17 at 14:28

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

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}$$