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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Anonymous Bunny
    Jun 29 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
    Jun 29 at 10:20
  • $\begingroup$ Is it not possible to generate constraints so that it works even for $e = 0$? $\endgroup$
    – Anonymous Bunny
    Jun 29 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 ♦
    Jun 29 at 15:58

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.