3
$\begingroup$

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$
  • 1
    $\begingroup$ Of course when $x_1=0,$ it cannot happen $x_1\ge10,$ so one can just use OR. $\endgroup$ – awllower Jul 6 '16 at 16:31
3
$\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$
  • $\begingroup$ 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$). $\endgroup$ – Kuifje Jul 7 '16 at 3:16
  • $\begingroup$ 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? $\endgroup$ – Bastian Jul 7 '16 at 18:27
  • $\begingroup$ @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. $\endgroup$ – Rodrigo de Azevedo Jul 7 '16 at 19:34
  • $\begingroup$ @Kuifje The question alluded to the Big M method. Erwin's approach is much simpler, but it does not use any big M's. $\endgroup$ – Rodrigo de Azevedo Jul 7 '16 at 19:59
  • $\begingroup$ @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 $$ $\endgroup$ – Kuifje Jul 7 '16 at 21:47
4
$\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$
1
$\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)$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bastian Jul 6 '16 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.