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?
$\endgroup$ 13 Answers
$\begingroup$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.
$\endgroup$ 11 $\begingroup$Using an extra binary variable $\delta$ we can write: \begin{align} & 10 \delta \le x_1 \le 300 \delta \\ &\delta \in \{0,1\} \end{align} $x_1$ is called a semi-continuous variable and some solvers support this directly without the need for extra binary variables.
$\endgroup$ $\begingroup$Note that $x_1 = 0$ and $x_1 \geq 10$ are mutually exclusive.
Writing the inequality constraints in Disjunctive Normal Form (DNF), we obtain
$$\begin{array}{rl} & (x_1 \leq 300 \land x_2 \leq 300) \land (x_1 = 0 \lor x_1 \geq 10) \equiv\\\\ \equiv& (x_1 = 0 \land x_2 \leq 300) \lor (10 \leq x_1 \leq 300 \land x_2 \leq 300)\end{array}$$
Thus, the feasible region is the union of a half-line and a polytope. Hence, we solve two linear programs, namely,
$$\begin{array}{ll} \text{maximize} & 1.5x_1 + 2x_2\\ \text{subject to} & x_1 = 0\\ & x_2 \leq 300\end{array}$$
and
$$\begin{array}{ll} \text{maximize} & 1.5x_1 + 2x_2\\ \text{subject to} & x_1, x_2 \leq 300\\ & x_1 \geq 10\end{array}$$
and then take the maximum of the maxima of each linear program:
over the half-line, the maximum is $600$, which is attained at $(0,300)$.
over the polytope, the maximum is $1050$, which is attained at $(300,300)$.
