# Minimum number of binary integer variables to handle $AND$ and $OR$ implications in Mixed Integer Linear Programming?

Suppose I want to have an integer program for handling the cases

1. $$(x_1>1)\wedge(x_2>1)\wedge(x_3>1)\wedge\dots\wedge(x_n>1)\implies\delta=1$$

2. $$(x_1>1)\vee(x_2>1)\vee(x_3>1)\vee\dots\vee(x_n>1)\implies\delta=1$$

3. $$(x_1>1)\wedge(x_2>1)\wedge(x_3>1)\wedge\dots\wedge(x_n>1)\iff\delta=1$$

4. $$(x_1>1)\vee(x_2>1)\vee(x_3>1)\vee\dots\vee(x_n>1)\iff\delta=1$$

how many number of integer variables are needed to handle case?

Is it possible at least one of them needs at most a constant number of binary variables?

• Are the $x_i$ real-valued or integer-valued? – prubin Apr 3 '19 at 19:32
• @prubin they are real valued. – T.... Apr 3 '19 at 21:36
• Strong inequalities with real valued variables are not typically allowed in math programs (since they result in open feasible regions). With integer variables, $x>1$ is the same as $x\ge 2$, which is why I asked. Are you interested in the case $x_n\ge 1$ etc., or willing to change to $x_n \ge 1+\epsilon$ etc. ($\epsilon$ a small positive constant)? – prubin Apr 4 '19 at 22:25

The following formulations assume that $$\delta \in \{0,1\}$$ and $$u_i$$ is an upper bound on $$x_i$$.
For #1, introduce $$n$$ binary variables $$y_i$$ and linear constraints: \begin{align} x_i - 1 &\le (u_i - 1) y_i &&\text{for i=1,\dots,n}\\ \sum_{i=1}^n y_i - n + 1 &\le \delta \end{align}
For #2, you do not need any additional variables: $$x_i - 1 \le (u_i - 1) \delta \quad \text{for i=1,\dots,n}$$
For #3 and #4, you need to consider @prubin's question about $$\epsilon$$.