Binary integer variables in linear programming

Question

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?

Answer 1

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.

Answer 2

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)$.

Answer 3

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.