如此链接所示，我们有一个问题表述。
考虑到第一次调用bintprog给出的解决方案x在经过一些后处理后不能充分解决物理问题，是否可以召回bintprog并排除先前的解决方案x？
问问题
467 次
1 回答
0
你需要一个不好的削减。
假设您找到了一个解决方案 \hat{x}，然后您认为该解决方案是不可行的（通过某种后处理）。让 x 和 \hat{x} 被 i 索引。
您可以添加以下形式的约束：
\sum_{i : \hat{x}_i = 0} x_i + \sum_{i : \hat{x} = 1} (1-x_i) \geq 1
这个约束是一个不好割的例子：解必须与 \hat{x} 相差至少一个索引 i，否则它是不可行的。如果您的变量不是二进制无货，则可能会更复杂一些。
您可以通过将约束作为一行附加到您的约束矩阵并使用 bintprog() 函数重新求解来为您的解决方案添加一个不好的东西。我会把它留给你，让你用 MATLAB 符号重写它。
你没有说你的后处理做了什么，但如果后处理可以从你的解决方案 \hat{x} 推断出其他解决方案也是不可行的，并且你可以在每次迭代中添加不止一行，那就更好了. 这是基于逻辑的 Benders 分解的一种形式，其他不可行解决方案的推理称为求解推理对偶（与标准 Benders 分解相反，您正在求解线性规划对偶）。 更多关于基于逻辑的 Benders 分解来自创造这个术语的人，CMU 的 John Hooker。
抱歉格式化。我得走了，但我以后会想办法更好地显示方程式。
于 2013-04-11T17:18:50.710 回答