I have a set of variables:
$x_1,x_2,x_3,x_4$
$x_1$ is a binary integer variable while the rest are real numbers all between $0$ and $1$.
I want a constraint such that:
if $x_2+x_3+x_4>0$ then $x_1=1$,
and
if $x_2+x_3+x_4=0$ then $x_1=0$.
[Math] Mixed Integer Linear Programming Conditional Constraints
integer programminglinear programminglogicmathematical modelingoperations research
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$
Such constraints are called disjunctive constraints. You can proceed as follows (for your constraint 1.):
$$ y_2+y_3+y_4\le2+(1-x_1)\quad y_2+y_3+y_4\ge2-2(1-x_1), $$
This way, if $x_1=1$, you have
$$ y_2+y_3+y_4\le2 \quad y_2+y_3+y_4\ge2, $$
which is equivalent to $y_2+y_3+y_4=2$. And if $x_1=0$, you have
$$ y_2+y_3+y_4\le2+1=3\quad y_2+y_3+y_4\ge2-2=0, $$
which will always be satisfied since variables are boolean.
Best Answer
You can write $$x_1=-\left\lfloor -{x_2+x_3+x_4\over 3}\right\rfloor$$which is equivalent to the following linear constraints:$$-x_1\le -{x_2+x_3+x_4\over 3}<-x_1+1$$or equivalently$$-3x_1+x_2+x_3+x_4\le 0\\-3x_1+x_2+x_3+x_4>-3$$