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?

  • $\begingroup$ Are the $x_i$ real-valued or integer-valued? $\endgroup$ – prubin Apr 3 '19 at 19:32
  • $\begingroup$ @prubin they are real valued. $\endgroup$ – T.... Apr 3 '19 at 21:36
  • $\begingroup$ 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)? $\endgroup$ – 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$.


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.