2
$\begingroup$

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

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

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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