3
$\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$
  • 1
    $\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$ – Erwin Kalvelagen Nov 2 '17 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 '17 at 0:40
9
$\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$

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.