在LP中设计线性约束强制至少一个自由变量非零可行吗？

首先明确结论：仅用线性约束无法实现“n个自由变量中至少有一个非零”的要求，原因如下：

线性规划的可行域是若干半空间的交集，属于凸集。而“所有变量全为零”的补集（即至少一个变量非零）是一个非凸集——例如取两个点$(1,0)$和$(-1,0)$，它们的凸组合是$(0,0)$，但这个组合点不在“至少一个变量非零”的集合中，违背了凸集的定义。因此这个非凸条件无法通过线性约束的交集来描述。

如果你的场景允许引入整数变量（即转向整数线性规划ILP），可以通过以下方式实现需求：

• 对每个自由变量$x_i$，引入一个二进制变量$z_i \in {0,1}$
• 为每个$x_i$添加约束：$|x_i| \leq M \cdot z_i$，其中$M$是一个足够大的常数（需大于$x_i$在可行域内可能取到的最大绝对值）
• 添加全局约束：$\sum_{i=1}^n z_i \geq 1$

这个逻辑是：当$z_i=0$时，$x_i$必须为0；当$z_i=1$时，$x_i$可以取任意允许的非零值。$\sum z_i \geq 1$保证了至少有一个$z_i=1$，从而避免了所有变量全零的情况。

需要注意的是，$M$的取值要合理：过大可能导致数值计算不稳定，过小则可能错误限制$x_i$的可行范围。

内容的提问来源于stack exchange，提问作者Naveed Ahmed Azam