计算 IIS
COPT 4.0 版本添加了计算不可行模型最小冲突集(Irreducible Inconsistent Subsystem,简称 IIS)的分析功能,支持线性规划和混合整数规划。
添加这项功能是因为在实际应用中,经常因为用户建模的错误或给定输入数据本身的冲突,导致构建的数学规划模型无解。一般来说,由于实际模型规模较大且约束关系复杂,难以人工分析出导致模型无解的原因,因此需要借助计算机进行辅助分析。该功能允许用户在给定的时间内找到一个导致模型不可行的极小冲突集,并且指明根本原因是哪些约束或变量的上/下边界,用户可以根据上述信息修改模型,最终使得模型可行。
例如下列写成 LP 格式的线性规划问题是一个不可行的问题(所有的变量 X 取值为非负)
尽管它只有 8 个变量,11 个约束,但如果要手动找到不可行的原因,任然是一个很难的事情。使用 COPT 的 IIS 工具,则可以计算出它的 IIS 为:
进一步分析这个小问题,根据约束 ROW1 推知 X4 ≤ 10000-0.8X3 ≤ 10000,根据 ROW5 推知 X4 ≥ 87000+X2 ≥ 87000,这两个矛盾的约束导致原始问题不可行。用户最终可以选择增大 ROW1 的 10000 或者减少 ROW5 的 87000 来修复不可行性。
注意,不可行模型可能存在多组 IIS,COPT 每次计算时只返回一组 IIS,用户可能需要根据返回的冲突原因多次修改模型与计算 IIS。
版权声明: 本文为 InfoQ 作者【杉数科技】的原创文章。
原文链接:【http://xie.infoq.cn/article/a3929a9cf2cb817f75c545db7】。文章转载请联系作者。
评论