How can the constraint: If x1=1 then x2+x3>=1 be written in linear programming if the variables x1,x2,x3 are binary?
[Math] If-then constraints with binary variables in Linear Programming
linear programming
Related Solutions
The possible constraints of a linear program are of the form $$ a^\top \, x \, \triangle \, \beta, \quad \triangle \in \{ =, \le, \ge \} $$ These are statements about the solution vector $x$ being part of the hyperplane or lying in a half space below or above an affine hyperplane with normal $a$.
Your constraints would require half a hyperplane only, which is not possible to express by a set of full hyperplanes.
Note: The following all include the constraints $x_i \in [0,1]$, restricting the search space to a cube.
Here is a visualization in $(x_1, x_2, x_6)$:
The search space is the union of the green square $x_6 = 0$ and the purple rectangle without bottom border $x_1 + x_2 = 1 \wedge x_6 > 0$. We can only model $x_1 + x_2 = 1$, but the extra part $x_1 + x_2 = 1 \wedge x_6 = 0$ is part of the first region, so we do not leave the search space. The solution can be found by running two optimizations and then selecting the best result.
This is a visualization of the second problem in $(x_1,x_2,x_3)$ only:
The search space is the union of the yellow square $x \mid x_2 = 0$ and the purple square without the foremost side $x_2 > 0 \wedge x_3 = 0$. Again run as two problems and pick the best solution.
For all variables we hope as well, to describe the search space as union of spaces that can be modelled by LP constraints.
- $X_1 = \{ x \mid x_2 = x_4 = x_6 = 0 \}$
- $X_2 = \{ x \mid x_2 > 0 \wedge x_3 = x_5 = x_7 = 0 \}$
- $X_3 = \{ x \mid x_2 = 0 \wedge x_4 > 0 \wedge x_5 = x_7 = 0 \}$
- $X_4 = \{ x \mid x_2 = x_4 = 0 \wedge x_6 > 0 \wedge x_7 = 0 \}$
This seems to be covering the whole search space $X$, e.g.
- $X_5 = \{ x \mid x_2 > 0 \wedge x_4 > 0 \wedge x_3 = x_5 = x_7 = 0 \subsetneq X_2$
- $X_6 = \{ x \mid x_2 > 0 \wedge x_6 > 0 \wedge x_3 = x_5 = x_7 = 0 \subsetneq X_2$
- $X_7 = \{ x \mid x_2 > 0 \wedge x_4 > 0 \wedge x_6 > 0 \wedge x_3 = x_5 = x_7 = 0 \subsetneq X_2$
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.
Best Answer
Here's a derivation via conjunctive normal form: \begin{equation} x_1 \implies (x_2 \lor x_3) \\ \neg x_1 \lor (x_2 \lor x_3) \\ (1 - x_1) + x_2 + x_3 \ge 1 \\ x_1 \le x_2 + x_3 \end{equation}