如何枚举可行域非空的非负变量子集不等式选择集合？

我来帮你一步步拆解这个问题，理清如何找出所有满足条件的相容选择集合：

我们有非负变量 (a_1,a_2,\dots,a_n \geq 0)，对每个子集 (S \subseteq [n])（这里([n])代表集合({1,2,\dots,n})），需要给它指定一个约束：要么是 (\sum_{i \in S}a_i \geq 1)，要么是 (\sum_{i \in S}a_i < 1)。我们的目标是找出所有这样的约束分配集合，使得对应的不等式组有至少一个可行解（即可行域非空）。

要判断一个约束集合是否相容，关键看被标记为(\sum_{i∈S}a_i≥1)的子集族的结构——它必须是一个上闭集（向上封闭族）。具体来说：

如果子集(S)被标记为(\sum≥1)，那么所有包含(S)的子集(T \supseteq S)也必须被标记为(\sum≥1)。

这是因为非负变量的子集和具有单调性：如果(S \subseteq T)，那么(\sum_{i∈S}a_i \leq \sum_{i∈T}a_i)。如果(S)的和已经≥1，那么更大的子集(T)的和肯定也≥1；反之如果(T)的和<1，那么更小的子集(S)的和也必然<1。

反过来，任何满足这个上闭集条件的约束集合都是相容的——我们总能构造出对应的可行解：

• 找出上闭集的极小元（即集合中不包含其他更小子集的元素）；
• 对每个极小元(S)，给其中的每个变量(a_i)分配(1/|S|)（(|S|)是子集(S)的大小），其他变量分配0；
• 这样构造的向量(a)会满足：所有属于上闭集的子集和≥1，其余子集和<1。

以你提到的(a_1,a_2)为例，所有相容的选择集合对应以下5种上闭集：

• 上闭集为空集：所有子集都标记为(\sum<1)，可行解比如(a_1=a_2=0.4)，所有子集和（0,0.4,0.4,0.8）都小于1。
• 上闭集=({{1},{1,2}})：标记(a_1≥1)、(a_1+a_2≥1)，其余标记<1，可行解(a_1=1,a_2=0)。
• 上闭集=({{2},{1,2}})：标记(a_2≥1)、(a_1+a_2≥1)，其余标记<1，可行解(a_2=1,a_1=0)。
• 上闭集=({{1,2}})：仅标记(a_1+a_2≥1)，其余标记<1，可行解(a_1=a_2=0.6)（和为1.2≥1，单个元素和0.6<1）。
• 上闭集=({{1},{2},{1,2}})：所有非空子集都标记为(\sum≥1)，可行解(a_1=a_2=1)，所有非空子集和≥1，空集和0<1。

要列出所有相容的选择集合，你可以按以下流程操作：

1. 枚举([n])的所有上闭集（向上封闭的子集族）；
2. 对每个上闭集，将集合内的所有子集标记为(\sum_{i∈S}a_i≥1)，其余子集标记为(\sum_{i∈S}a_i<1)；
3. 所有这样得到的约束集合就是全部相容的选择集合，不会有遗漏或错误。

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