整数线性规划中，多约束至少满足其一的M值求解方法

核心逻辑 #

M的作用是：当q_i=1（对应约束无需强制满足）时，让转化后的约束自动成立，无论变量x1~x4取什么合理值；当q_i=0时，约束还原为原始形式。因此M的取值需要根据约束类型和变量的可行范围来确定。

分约束类型计算M #

1. 对于≤型约束（如约束1、3）

原始约束：左边 ≤ 原上界
转化后：左边 ≤ 原上界 + M*q_i
当q_i=1时，需要原上界 + M ≥ 左边的最大可能值（即左边能达到的最大值），这样不管x取什么值，不等式都成立。
因此：M ≥ (左边的最大值) - 原上界

以约束1为例：
原上界是30，左边是x1+x2+x3+x4。如果x变量有明确上限（比如每个x_i≤100），则左边最大值是400，那么M≥400-30=370。

2. 对于≥型约束（如约束2）

原始约束：左边 ≥ 原下界
转化后：左边 ≥ 原下界 + M*q_i
当q_i=1时，需要原下界 + M ≤ 左边的最小可能值（即左边能达到的最小值），这样不等式自动成立。
因此：M ≤ (左边的最小值) - 原下界

这里注意：如果x变量无下界（比如x1可以取很大的负数），左边的最小值会是负无穷，此时M无法确定——实际问题中变量必然有隐含上下限（比如生产数量非负、资源总量有限），必须先明确这些范围。

另外，你当前的转化式可能存在符号混淆，更直观的写法是把≥型约束放松为：左边 ≥ 原下界 - M'*q_i（其中M'是正数），这样当q_i=1时，下界降低，约束更容易满足，M'的取值只需M' ≥ 原下界 - 左边的最小值，更符合直觉。

关键注意事项 #

• 不要选过大/过小的M：极端值会导致线性规划模型的数值稳定性问题（比如基矩阵条件数变差，求解器报错）。
• 优先用变量的实际范围：如果问题有实际背景（如x是生产数量、资源分配量），直接用业务场景中的合理上下限计算极值，比估算超大值更靠谱。
• 测试验证：确定M后，测试两种场景：q_i=0时约束是否等价于原始约束；q_i=1时约束是否真的不限制x的取值。

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