Binary variables allow us to model all sorts of logical conditions as linear programs. Let $x,y$ be binary integer variables.
First the most simple condition. We want a new binary integer variable $z$ such that $z = NOT(x)$
$$z = 1-x$$Let $z = x \text{ or } y$ $$ z \geq x \\ z \geq y \\ z \leq x+y$$
If x and y are both 0, then z must be 0 by the third condition. If on the other hand either x or y is 1 then z must be 1 by the first and second conditions. If x and y are both 1, the first two conditions hold and the third just states that $z \leq 2$ which is always going to be true. This new variable is effectively the larger of x and y. With negation and or, we have all we need to be functionally complete. Buts lets list the other basic logical operators out.
Let $z = x \text{ and } y$ $$ z \leq x \\ z \leq y \\ z \geq x+y - 1$$
$x$ or $y$ but not both, $$x+y \leq 1$$
If x is true, they y must be true, and if x is false y can be anything. This is satisfied by $$y \geq x$$
Crazy right? This is obviously non-linear, but we can handle two special cases.
$z = b*x$ where $b$ is binary and $x$ is continuous
let $x \in [A,B]$ and $z$ a continuous variable with the same bounds as x
$$bA \leq z \leq bB \\ (1-b)A \leq x-z \leq (1-b)B$$The first condition essentially turns off the output variable $z$ if the the binary variable $b$ is false. The second is a bit more mysterious, It places a bound on how far away $x$ can be from $z$. If $b=1$ then this bound tightens to 0.
$z = b1*b2$ where both variables are binary
$$z \leq b1 \\ z \leq b2 \\ z \geq b1+b2 -1$$This should look familiar, the product of two binary variables is the same as a logical AND
Logical constraints for continuous variables are considerably harder to model. When I say constraints for continuous variables I mean new constraints of the form, F(x,y) or G(x,y). Where the or is interpreted as either, here we are not seeking to create a new variable.
Suppose we have two constraints, and we only want to enforce one of them depending on the result of binary variable $b$.
i.e., if $b=1$ then we want $F(x) \geq 0$ and when $b=0$ we want $G(x) \geq 0$
We need to place a bound on both $F$ and $G$, ie we need an $M$ such that $|F| \leq M$ and $|G| \leq M$.
We then form: $$F(x) \geq -M(1-b) \\ G(x) \geq -M(b)$$
If $b=1$, then we will have $F(x) \geq 0$ and $G(x) \geq -M$
Lets assume for the moment that $|x| \leq 100$ so lets make $M=1000$
The form laid out above was a general form, we can transform the inequalities to match by multiplying by -1 and move constants around to get to 0. Of course we don't need to do that, the general idea of this big M method can be applied directly once it becomes intuitive. For now, lets transform the constraints to the form expected by the big M method.
$$ x - 10 \geq 0 \\ \text{or}\\ 20-x \geq 0$$Which gives us
$$x-10 \geq -M(1-b) \\ 20 - x \geq -M(b) \\$$Lets rewrite them back in the original form in which they were presented
$$x \geq 10 - M(1-b) \\ x \leq 20 + M(b)$$If $b=1$ then we get: $$x \geq 10 \\ x \leq 20 + M \leq 1020$$
Since $x \leq 100$ to start with, the additional second constraint effectively does nothing.
If $b=0$ then we get: $$x \geq 10-M \geq 10-1000 \geq -990\\ x \leq 20$$
Again the additional information that x be larger than a really negative number does not add anything new.
How big should this $M$ value be? In practice this is a number that is big in the context of the variables and expressions being used. In our example we could have used 120 and gotten away with it because while $x$ was bounded between -100 and 100, $|x-20|$ is bounded by 120. This number doesn't need to be exact, but don't use ten billion if the variables and expressions are close to 100 as doing so will make the problem harder to solve.
In this example we rearranged the inequalities to give so that they were all greater than or equal to. There is a handy shortcut to adding the M's. If the inequality is greater than or equal, then subtract the M because when the M. The intuition here should be that when M's condition is triggered we will be asking for a constraint that is larger than a really negative number which should always be true and therefore not add anything new. If on the other hand the inequality is less than or equal to, we need to add the M: When it is triggered we will need to be less than some really large number, also always true.
Lets do another example:
$$x + 10y \leq 15 \\ \text{or} \\3x - 8y \geq 9$$This becomes: $$x + 10y \leq 15 + M(1-b) \\3x - 8y \geq 9 - M(b)$$
If $b=1$ then: $$x + 10y \leq 15 \\3x - 8y \geq 9 - M = \text{really negative number}$$
If $b=0$ then: $$x + 10y \leq 15 + M = \text{really big number} \\3x - 8y \geq 9$$
Suppose we want to model $(A \leq x \leq B) \text{ or } (C \leq x \leq D)$ In other words, we want to have a continous variable that takes on only specified ranges of values. We can introduce a new binary variable $b$ which will select the interval x is in:
$$b = \begin{cases} 0 \text{ if } A \leq x \leq B \\ 1 \text{ if } C \leq x \leq D \end{cases}$$The constraint for x becomes $$ A + (C-A)b \leq x \leq B + (D- B)b$$
This is just a handy special case of the big M method with a very specific M for the lower bound and upper bound
In [ ]: