9
$\begingroup$

How to write the following if-else condition in Linear Programming? If $a > b$ then $c = d$ else $c = e$

$d$, $e$ are variables. How can we write a linear program without multiplying d and e with binary variables? But we can use binary variables.

$a,b,c,d,e > 0$

$\endgroup$
2
  • 3
    $\begingroup$ In general this can not be done in a pure continuous LP. You need binary variables to overcome the non-convexity in this construct. Some very special cases may not need binary variables. $\endgroup$ Nov 2, 2017 at 0:13
  • $\begingroup$ We can use binary variables but I don't want to multiply those binary variables with d or e because they too are variables in my problem. If we multiply binary variables with d or e the problem will lose linearity. $\endgroup$
    – Vinay
    Nov 2, 2017 at 0:40

1 Answer 1

24
$\begingroup$

This can not be formulated as a linear programming problem. We need extra binary variables and end up with a MIP.

First we do:

$$ a > b \Longleftrightarrow \delta = 1$$

This can be formulated as: $$\begin{align} &a \ge b + 0.001 - M(1-\delta)\\ &a \le b + M\delta\\ &\delta \in \{0,1\} \end{align}$$ (in practice I would drop the $0.001$ term).

Next we do: $$\begin{align} &\delta=1 \Longrightarrow c=d\\ &\delta=0 \Longrightarrow c=e \end{align}$$ This can be written as: $$\begin{align} & d-M(1-\delta)\le c \le d + M(1-\delta)\\ & e-M\delta\le c \le e + M\delta\\ \end{align}$$

Many modern MIP solvers have indicator constraints. This can make things easier as one can write implications directly without big-M constraints.

$\endgroup$
3
  • 1
    $\begingroup$ @Erwin....how can we formulate, If a = b then c = d else c = e ? $\endgroup$
    – Vinay
    Mar 24, 2020 at 18:19
  • $\begingroup$ In a similar way. Use something like $ \delta = 0 \implies a=b, c=d$ and $ \delta = 0 \implies a \ne b, c=e$. $\endgroup$ Mar 27, 2020 at 23:54
  • $\begingroup$ I was expecting something more like this $\endgroup$
    – Vinay
    Mar 28, 2020 at 3:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .