添加解决方案作为约束以枚举线性规划 problem 的解决方案
Adding solutions as constraints to enumerate solutions to a linear programming problem
我已经设法将问题建模为具有二进制变量的 LP 问题并解决了它（使用 PuLP 和 GLPK）。我相信我在某处读到过，您可以 "add your solution as a new constraint" 让求解器提出替代解决方案。不幸的是，我找不到我在哪里读到这篇文章，我也看不到如何 "add the solution" 来阻止求解器使用以前的解决方案。如果我读到的是正确的，有人可以解释一下如何做到这一点吗？
我对 LP 很陌生。我已经搜索过答案，但很可能我失败了，因为我不知道正确的搜索词。我知道通常枚举解决方案 space 是不可行的，因为 space 的大小非常大。我只是想知道如何 "add a solution" 来防止求解器再次找到它。
您可以为您的问题添加一个 objective 中断，这将使您之前的解决方案不可行，但这很可能也会中断其他解决方案 - 特别是对于退化问题。
This 是一个密切相关的问题，可能会有帮助。有关如何添加 objective 截止值的想法，请参阅我的回答。
具有二进制变量的 LP 不再是 LP（而是 MIP）。禁止先前找到的整数解 x*(i) 的约束可以表述如下。
- 令
P subset of I 为对应于索引x*(i)=1 的集合。
- 设
Q subset of I 为索引对应的集合，其中 x*(i)=0.
显然P+Q=I。向模型添加以下约束：
sum(i in P, x(i)) - sum(i in Q, x(i)) <= p - 1
其中 p 是集合 P 的基数（元素数）。这个约束的推导是here.
我已经设法将问题建模为具有二进制变量的 LP 问题并解决了它（使用 PuLP 和 GLPK）。我相信我在某处读到过，您可以 "add your solution as a new constraint" 让求解器提出替代解决方案。不幸的是，我找不到我在哪里读到这篇文章，我也看不到如何 "add the solution" 来阻止求解器使用以前的解决方案。如果我读到的是正确的，有人可以解释一下如何做到这一点吗？
我对 LP 很陌生。我已经搜索过答案，但很可能我失败了，因为我不知道正确的搜索词。我知道通常枚举解决方案 space 是不可行的，因为 space 的大小非常大。我只是想知道如何 "add a solution" 来防止求解器再次找到它。
您可以为您的问题添加一个 objective 中断，这将使您之前的解决方案不可行，但这很可能也会中断其他解决方案 - 特别是对于退化问题。
This 是一个密切相关的问题，可能会有帮助。有关如何添加 objective 截止值的想法，请参阅我的回答。
具有二进制变量的 LP 不再是 LP（而是 MIP）。禁止先前找到的整数解 x*(i) 的约束可以表述如下。
- 令
P subset of I为对应于索引x*(i)=1的集合。 - 设
Q subset of I为索引对应的集合，其中x*(i)=0.
显然P+Q=I。向模型添加以下约束：
sum(i in P, x(i)) - sum(i in Q, x(i)) <= p - 1
其中 p 是集合 P 的基数（元素数）。这个约束的推导是here.