CBC - 知道“为什么”一个程序不可行

Question

我使用 CBC 来解决不同的整数线性规划问题。对于其中一些，约束集是没有解决方案的。在这种情况下，我得到如下信息：

Problem is infeasible - 0.30 seconds
Infeasible - objective value -6832.50000000

CBC 有什么办法可以告诉我“为什么”这个问题不可行？例如，我很乐意拥有一组不兼容的最小约束。

Answer 1

我很确定，此功能未在 CBC 中实现。

替代软件

不过，Cplex和Gurobi支持这个概念。对于后者，我可以确认，这非常有效（称为Irreducible Inconsistent Subsystem (IIS)）。如果您处于学术环境中（您的访问域需要被识别为大学）并且您的项目符合学术项目的条件（总是最好自己查看使用条款），Gurobi 也可以免费使用。

自定义实现

如果你想自己实现这个，看看：

O. Guieu 和 JW Chinneck (1999)，“分析不可行的混合整数和整数线性程序”，INFORMS 计算杂志，第一卷。11，没有。1，第 63-77 页。

或者

乌尔里希·容克。2004. QUICKXPLAIN：对过度约束问题的首选解释和放松。在第 19 届全国人工智能会议论文集 (AAAI'04) 中，Anthony G. Cohn (Ed.)。AAAI 出版社 167-172。

后者在cbc 的这个 Ruby 包装器中实现