我怎么知道是否还有更多的解决方案？

Question

我用线性规划做了爱因斯坦的谜题练习。我在Gusek实现了这个解决方案。如何判断是否有多个解决方案？

Einsten的谜语：

有五种不同颜色的房子。每户人家都住着一个不同国籍的人。这五个主人喝某种饮料，抽某种牌子的雪茄，养一只宠物。没有主人有同样的宠物，抽同样牌子的雪茄，或者喝同样的饮料。

约束：

英国人住在红房子里

瑞典人养狗当宠物

丹麦人喝茶

绿屋在白宫的左边。

绿屋的主人喝咖啡

抽烟的人养鸟

这座黄色房子的主人抽烟。

住在中心的那个人喝牛奶。

挪威人住在第一栋房子里

抽烟的人住在养猫的旁边。

养马的人住在抽烟的人旁边。

抽BlueMaster烟的人喝啤酒

德国人吸烟王子

挪威人住在蓝房子旁边

抽烟的人有一个喝水的邻居

我能告诉你哪些约束是多余的吗？

谢谢你的帮助

Answer 1

您的决策/解决方案将以二进制或整数变量的形式出现。

如果它们是二进制的，那么添加一个新的约束，如下所示：(Y是所有为1的二进制文件，‘Y是0的二进制文件。)

sum(Y) +sum(i-Y) != |Y|+|Y_x)

继续重复，直到你得到一个不可行的模型。这也可以扩展到整数的情况。

至于冗余，您必须手动尝试删除它们，并查看解决方案是否更改。但是，就reduncancy而言，您可能会遇到约束A和B是冗余的情况，或者约束C是冗余的。根据消除的不同，可以有多组潜在的冗余约束。