无辅助变量构建二进制变量约束：资源分配模型咨询

Great question—avoiding extra variables when n is large is a smart move to keep your model tractable and efficient. Let’s break down how to translate your logical constraint into linear constraints using only your existing binary $x_i$ variables:

Case 1: $k \leq 1$ #

Your constraint is automatically satisfied. If any $x_i = 1$, the sum $\sum_{i=1}^n x_i$ is at least 1, which is already greater than or equal to $k$. No need to add any constraints here.

Case 2: $1 < k \leq n$ #

First, since $\sum_{i=1}^n x_i$ is an integer (all $x_i$ are 0 or 1), requiring $\sum x_i \geq k$ is equivalent to $\sum x_i \geq s$, where $s = \lceil k \rceil$ (the smallest integer that’s greater than or equal to $k$).

Your core rule is: If any $x_i = 1$, then the total sum must be at least $s$. This is the same as saying: If the total sum is less than $s$, then all $x_i$ must be 0.

To model this without auxiliary variables, add the following $n$ linear constraints (one for each $x_i$):
$$x_i \leq \frac{1}{s} \sum_{j=1}^n x_j \quad \forall i \in [1,n]$$

Why this works: #

• When $\sum x_i \geq s$: The right-hand side $\frac{1}{s}\sum x_j$ is at least 1. Since $x_i$ is binary (0 or 1), this constraint is automatically satisfied (0 ≤ 1+, 1 ≤ 1+).
• When $\sum x_i \leq s-1$: The right-hand side $\frac{1}{s}\sum x_j$ is less than 1. Since $x_i$ can only be 0 or 1, this forces every $x_i$ to be 0—exactly what we need to enforce the original rule.

Case 3: $k > n$ #

The maximum possible sum of $x_i$ is $n$ (when all are 1), which is less than $k$. This means your constraint forces all $x_i$ to be 0. Just add this simple constraint for every $i$:
$$x_i = 0$$

Quick Example #

Let’s say $n=5$, $k=3.2$ (so $s=4$). The constraints become:
$$x_1 \leq 0.25(x_1+x_2+x_3+x_4+x_5)$$
$$x_2 \leq 0.25(x_1+x_2+x_3+x_4+x_5)$$
$$...$$
$$x_5 \leq 0.25(x_1+x_2+x_3+x_4+x_5)$$
If the sum is 3 (less than 4), each right-hand side is 0.75, so all $x_i$ must be 0. If the sum is 4 or 5, the right-hand side is ≥1, so the constraints don’t restrict the $x_i$s at all.

内容的提问来源于stack exchange，提问作者dee901