Could someone please explain the concept of switch variables (binary integer decision variables) in linear programming?
This example has two alternative constraints
$$\begin{array}{ll} \text{maximize} & 1.5x_1 + 2x_2\\ \text{subject to} & x_1, x_2 \leq 300\\ & x_1 = 0 \quad \mbox{XOR} \quad x_1 \geq 10\end{array}$$
I have seen examples of solutions for such tasks by applying something like following:
$$x_1+My_1 = 0\\x_1 – My_1 \geq 10+M$$
Does someone know and understand this approach and can explain it to me?
Best Answer
Note that
$$\begin{array}{rl} x_1 = 0 \lor x_1 \geq 10 &\equiv (x_1 \geq 0 \land x_1 \leq 0) \lor x_1 \geq 10\\\\ &\equiv x_1 \geq 0 \land (x_1 \leq 0 \lor x_1 \geq 10)\end{array}$$
We can handle the disjunction $x_1 \leq 0 \lor x_1 \geq 10$ using the Big M method. We introduce binary variables $z_1, z_2 \in \{0,1\}$ such that $z_1 + z_2 = 1$, i.e., either $(z_1,z_2) = (1,0)$ or $(z_1,z_2) = (0,1)$. We introduce also a large constant $M \gg 10$ so that we can write the disjunction in the form
$$x_1 \leq M z_1 \land x_1 \geq 10 - M z_2$$
If $(z_1,z_2) = (1,0)$, we have $x_1 \leq M$ and $x_1 \geq 10$, which is roughly "equivalent" to $x_1 \geq 10$. If $(z_1,z_2) = (0,1)$, we have $x_1 \leq 0$ and $x_1 \geq 10 - M$, which is roughly "equivalent" to $x_1 \leq 0$.
Thus, we have a mixed-integer linear program (MILP)
$$\begin{array}{ll} \text{maximize} & 1.5x_1 + 2x_2\\ \text{subject to} & x_1, x_2 \leq 300\\ & x_1 \geq 0\\ & x_1 - M z_1\leq 0\\ & x_1 + M z_2 \geq 10\\ & z_1 + z_2 = 1\\ & z_1, z_2 \in \{0,1\}\end{array}$$
For a quick overview of MILP, read Mixed-Integer Programming for Control by Arthur Richards and Jonathan How.