0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Are the $x_i$ real-valued or integer-valued? $\endgroup$ Commented Apr 3, 2019 at 19:32
  • $\begingroup$ @prubin they are real valued. $\endgroup$ Commented Apr 3, 2019 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$ Commented Apr 4, 2019 at 22:25

1 Answer 1

Reset to default
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.