Minizinc+Cplex求解ILP时目标值随约束阈值异常变化的问询

你的问题核心是最小值操作的线性化约束不完整，导致模型可行域被过度松弛，求解器误判了最优解：

• 未添加objective_term >= c约束时，模型仅对目标项（由min操作线性化而来）添加了上界约束（比如z <= a、z <= b），但缺失了强制z取到min(a,b)的下界紧约束。这使得求解器可以选择让z取比真实min(a,b)更小的值，在最大化目标时，找到z=1的整数解就判定为最优——但实际上存在满足原问题逻辑的z=2的解，只是模型没约束求解器去探索该可行域。
• 添加objective_term >= c后，相当于手动给z加上了下界约束，当c增大到2时，求解器被迫寻找满足z>=2的可行解，而该解确实存在，因此能返回目标值2并宣称最优；当c超过真实最大值时，自然返回UNSATISFIABLE。
• 强制二进制变量为1能得到更优解，说明这个二进制变量是线性化min操作时引入的开关变量，原模型未约束该变量的取值逻辑，导致求解器默认选择了让z更小的变量取值（比如开关变量为0，压低下界），而非能让z取到更大值的取值。

要确保ILP模型能找到真实最优解，编码必须满足以下核心条件：

• 约束完备性：所有原问题的非线性逻辑（如min/max、条件判断）必须被完整线性化，不能遗漏关键约束。比如对z = min(a,b)的线性化，除了z <= a、z <= b，还需针对整数场景添加下界约束（如引入二进制变量x，添加z >= a - M*(1-x)、z >= b - M*x，其中M是合理的大常数），确保z的取值完全等价于原min操作的结果。
• 约束紧致性：线性化时使用的大M值要尽可能小（但需保证约束逻辑成立），过大的M会导致连续松弛解的质量下降，求解器更容易找到假最优解或陷入低效搜索。
• 目标一致性：目标函数必须准确对应原问题的优化目标，不能因线性化操作引入额外偏差或无关项。
• 整数约束正确性：所有需要取整的变量必须正确标记为整数/二进制类型，且约束不能允许不符合原问题逻辑的整数解进入可行域。

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