Consecutive binary variables, without using auxiliary variables

Question

I have $i = 1,.....,n $ binary variables $x_{i}=\{0,1\}$ that I am using the model a resource allocation problem.

I am struggling with the constraint that if $\exists i\in[1,n]$ such that $x_{i}=1$ then $$\sum_{i=1}^n x_{i} \ge k,$$ $k\in \mathbb{R}$.

I have read through some similar problems like: How to model a consecutive binary constraint? but the suggestion is to add auxiliary variables. The value of $n$ is currently large and I would not like to increase it with more variables.

Answer 1

Let $m=\lceil k \rceil$

If $m\leq 2$ and $n \geq m$

$\forall S \subset [1,n], |S| = n - (m - 1)$

$\displaystyle\sum_{i\in S}x_i - x_j \geq 0\;\;\;\forall j\notin S$ describe your problem (with the binary variables constraints)

If $x_j = 1$, $\displaystyle\sum_{i\in S}x_i - x_j \geq 0$ because there is only $m-1$ variables not in $S$

The 0 - vector also verify this constraint

If a vector does not verify your constraint, there is less than $m-1$ variables equal to 1, and there exist $x_j = 1$.

Then, we have $\displaystyle\sum_{i\in S}x_i - x_j < 0 $ where S has no variable equal to 1.

I think those constraints are all facets, except the ones coming from the binary variables.

Answer 2

The way I read (or misread) your problem is that $$z = \sum_i x_i$$ where $z=0$ or $k \le z \le n$. This is the same as saying $z$ is a semi-continuous variable with bounds $k$ and $n$. Most MIP solvers support semi-continuous variables directly. Otherwise you can do:

$$\begin{align} & k\cdot \delta \le z \le n\cdot \delta\\ &\delta \in \{0,1\}\\ & 0 \le z \le n \end{align} $$