CBC-了解“为什么"程序不可行 [英] CBC - know "why" a program is infeasible

问题描述

我使用CBC解决不同的整数线性规划问题.对于其中的某些约束而言，这是没有解决方案的.在这种情况下，我得到的是这样的:

I use CBC to solve different integer linear programming problems. For some of them, the set of constraints is such that there is no solution. In this case, I get something like this:

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

CBC有什么办法可以以某种方式告诉我为什么"这个问题不可行?例如，我很乐意拥有一组不兼容的最小约束.

Is there any way CBC can tell me somehow "why" the problem is infeasible? For example, I would be happy to have a minimal set of constraints that are incompatible.

推荐答案

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

I'm pretty sure, this functionality is not implemented in CBC.

Cplex 和 Gurobi .对于后者，我可以确认，这非常有效(称为不可还原的不一致子系统(IIS)).如果您处于学术环境中(您的访问域需要被承认为大学)并且您的项目符合学术项目的资格(总是最好自己检查使用条款)，也可以免费使用Gurobi.

There is support for this concept in Cplex and Gurobi though. For the latter i can confirm, that this works quite well (called Irreducible Inconsistent Subsystem (IIS)). Gurobi is also available without costs if you are in an academic setting (your access-domain needs to be recognized as university) and your project qualifies as academic project (always better to check out the terms of usage yourself).

如果您想自己实现，请查看:

If you want to implement this yourself, have a look at:

O.Guieu和J.W.Chinneck(1999)，分析不可行的混合整数和整数线性程序"，《 INFORMS计算学报》，第11卷，第1期.1，第63-77页.

O. Guieu and J.W. Chinneck (1999), "Analyzing Infeasible Mixed-Integer and Integer Linear Programs", INFORMS Journal on Computing, vol. 11, no. 1, pp. 63-77.

或

乌尔里希·容克.2004年.QUICKXPLAIN:对过度约束的问题的首选解释和放松.在第19届全国人工智能会议(AAAI'04)的会议记录中，Anthony G. Cohn(编辑).AAAI按167-172.

Ulrich Junker. 2004. QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In Proceedings of the 19th national conference on Artifical intelligence (AAAI'04), Anthony G. Cohn (Ed.). AAAI Press 167-172.

后者在用于bbc的Ruby包装器中实现

这篇关于CBC-了解“为什么"程序不可行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！