2
$\begingroup$

I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP

$$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \text{if } d < e \end{cases} $$

where $c \in \{0,1\}$ is a binary variable, $d \in [0,1]$ is a continuous variable, and $e \in [0, 1]$ is given. How should I do this? In the constraints, I want only $\geq$, $\leq$, $=$, $<$, and $>$.

I have tried consulting various resources, but they generally only talked about if-then scenarios and not this one.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

For more clarity, I have slightly changed the notations: $y_c \in \{0,1\}$ is the binary variable $c$ and $x_d \in [0,1]$ is the continuous variable $d$. I will also assume that $0<e\le 1$ to avoid ambiguity at the breakpoint $e=0$.

You want to enforce $$ (x_d \ge e \implies y_c=1) \wedge (x_d < e \implies y_c=0) $$ which is equivalent (via contraposition) to $$ (y_c=0 \implies x_d < e) \wedge (y_c=1 \implies e\le x_d) $$ You can enforce $y_c=1 \implies e\le x_d$ with: $$ e \le x_d + (1-y_c) $$ And $y_c=0 \implies x_d < e$ with: $$ x_d -y_c < e $$ Finally, the resulting constraint is: $$ x_d+\epsilon -y_c\le e \le x_d + (1-y_c) $$ where $\epsilon$ is your tolerance.

$\endgroup$
4
  • $\begingroup$ Hi, thanks a lot for your solution. But there's a slight problem: When $x_{d} = 1$ and $e = 0$, we want $y_{c}$ to be $1$. However, the second condition ($x_{d} - y_{c} < e$) is not satisfied when $y_{c}=1$ since $x_{d} - y_{c} = 1 - 1 = 0$ $! < 0 = e$ $\endgroup$ Commented Jun 29, 2023 at 9:56
  • $\begingroup$ Yes this breakpoint is ambiguous. I have added a comment to specify that the formulation is valid for $e>0$. $\endgroup$
    – Kuifje
    Commented Jun 29, 2023 at 10:20
  • $\begingroup$ Is it not possible to generate constraints so that it works even for $e = 0$? $\endgroup$ Commented Jun 29, 2023 at 10:23
  • 1
    $\begingroup$ @AnonymousBunny No, that is not possible. For various reasons, mathematical programs require weak, not strong, inequalities. Even if it were theoretically possible, the limits of double-precision arithmetic would result in values of $x_d$ near $e$ appearing to equal (or even exceed) $e.$ So you need to choose $epsilon > 0$ large enough to prevent rounding error from causing incorrect results, and you are stuck with $(e - \epsilon, e)$ being removed from the domain of $x_d.$ $\endgroup$
    – prubin
    Commented Jun 29, 2023 at 15:58

Your Answer

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

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