Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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}$$
