写点什么

计算 IIS

作者:杉数科技
  • 2022 年 2 月 23 日
  • 本文字数:515 字

    阅读完需:约 2 分钟

计算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。

发布于: 刚刚阅读数: 3
用户头像

杉数科技

关注

服务逾20个行业的超100家龙头企业 2021.04.07 加入

杉数科技,是中国领先的人工智能决策优化技术服务企业,通过中国首个自研商用求解器COPT,为企业打造从数据到决策的端到端决策产品平台,帮助客户解决一系列业务场景中的决策优化难题,进一步助力企业降本增效。

评论

发布
暂无评论
计算IIS