# Binary integer variables in linear programming

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?

• Of course when $x_1=0,$ it cannot happen $x_1\ge10,$ so one can just use OR. – awllower Jul 6 '16 at 16:31

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.

• If you set $M$ to $300$ in the third constraint and $M$ to $10$ in the fourth constraint, and replace $z_2$ by $1-z_1$, you end up with exactly Erwin Kalvelagen's solution (his $\delta$ is your $z_1$). – Kuifje Jul 7 '16 at 3:16
• Would it change anything if the first of the alternative constraints (x1 = 0) would have a value higher than zero at the right hand side? – Bastian Jul 7 '16 at 18:27
• @BastianSchoettle How much higher? Read my other answer to this question. If $x_1 = a$, where $a \in [10, 300]$, then the half-line is inside the polytope. Enlarging the feasible region cannot decrease the maximum. – Rodrigo de Azevedo Jul 7 '16 at 19:34
• @Kuifje The question alluded to the Big M method. Erwin's approach is much simpler, but it does not use any big M's. – Rodrigo de Azevedo Jul 7 '16 at 19:59
• @Rodrigo de Azevedo: Erwin's approach IS a big $M$ method, with specific values of $M$. As I mentioned above: if the first $M$ equals $300$, then you have $$x_1-300z_1\le 0$$ If the second equals $10$ then you have $$x_1+10z_2\ge 10$$ Now given that $z_1=1-z_1$, both equations are equivalent to $$10z_1\le x_1\le 300z_1$$ – Kuifje Jul 7 '16 at 21:47

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.

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

• Thank you for the formatting and your explanation but I need to solve this task in a single model. I've updated my answer accordingly. – Bastian Jul 6 '16 at 19:10