优化问题含整数变量的约束转化为二元变量约束的方法及正确性核验

模型基础情况 #

• 正在搭建的优化模型包含多组约束，决策变量同时分为两类：一类是取值为0/1的二元变量y，另一类是取整数值的整数变量ŷ
• 你手头持有原始问题的公式截图、自行推导的简化约束截图作为参考材料
• 当前针对原始问题中编号为(12)的约束做简化处理

简化目标 #

• 彻底从约束(12)中消去整数变量ŷ，将约束改写为只包含二元变量y的形式
• 核验你自行推导的简化版本约束，判断其与原约束是否完全等价

等价性核验的可落地方法 #

• 双向充要校验
  • 正向验证：所有能让原约束(12)成立的二元变量组合，必须全部满足你推导的简化约束，不能把本来可行的解误筛出去
  • 反向验证：所有满足简化约束的二元变量组合，一定能找到对应的整数变量ŷ取值，让原约束(12)成立，不能把本来在原体系下不可行的解放进来
• 临界边界扫查
  • 逐个测试二元变量的极端取值场景（全取0、全取1、单个变量取值翻转的边界场景），对比原约束和简化约束的可行域边界是否完全一致
  • 重点核对ŷ取上下限临界值的场景，排查转化时容易出现的约束过紧、过松的问题

常见转化踩坑点 #

• 消元时容易遗漏ŷ和二元变量的绑定边界，让约束变形
• 容易把单向成立的必要条件当成双向充要条件——比如只保留单侧的不等式约束，往往会让简化后的可行域比原约束大，最后算出来的结果和原模型不匹配，这也是混合整数约束转化时最容易出现的等价性偏差来源

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