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$
  • 1
    $\begingroup$ What about $y \leq 5-x$? $\endgroup$ – Eugene Mar 30 '17 at 8:30
  • $\begingroup$ @Eugene This ensures that $y = 0$ if $x = 5$, but doesn't ensure that $y = 1$ otherwise. $\endgroup$ – Yuval Filmus Mar 30 '17 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 '17 at 14:28
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, privacy policy and cookie policy

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