0

我正在用 CPLEX（使用 Java）解决一个经典的网络流问题。它包含约束 Ax=b（A 是节点弧关联矩阵，x 是链路流的决策变量，b 是给定的右手边）。我对在一维中减少/减少 b 的阴影奖感兴趣。

在非退化问题中，影子价格由约束 Ax=b 上的对偶变量给出。但是，我的问题是退化的。因此，一个最优解可以由基础和非基础变量的几种组合来表示。这些组合中的每一个都应该有不同的对偶变量。

至少这些对偶中的一个应该给我 a 增加 b 的影子价格，另一个对偶将提供减少 b 的影子价格。（根据 W.Powell (1989)：“线性网络敏感性结果的回顾和减少退化影响的新近似”）

我的问题是：在用 CPLEX 求解 LP 并获得第一组对偶后，如何让 CPLEX 执行基变量和非基变量的交换，以便获得另一组对偶？

4

1 回答 1

2

下面的整个讨论都涉及对偶问题。

零成本降低的非基础变量可以在正水平上进入基础并形成替代最优解。因此，如果问题的最优目标值为 z* 并且 c'x 是相关的目标函数，则可以添加约束 c'x = z*，将目标函数更改为不同的目标函数，让单纯形执行一次迭代，然后进行迭代。第二次之后的每次迭代都应该（i）生成一个新的最优解或（ii）生成一个已经生成的最优解，在这种情况下，我们可以改变目标函数并进行迭代。

此处描述了此技术，并参考了 C API 函数：

对于线性程序，非基本变量的零成本降低表明存在替代的最优基。此外，您可以使用例程 CPXgetgrad 和 CPXgetx 来确定关联的枢轴是否退化（在这种情况下，解值保持不变，但基值发生变化）或不（在这种情况下，解值和基值都发生变化）。请注意，松弛变量的成本降低是相关对偶变量的负数。此外，例程 CPXaddrows 提供了一种简单的方法来枚举替代的最佳解决方案。假设原问题的最优目标值为z*，c'x为相关目标函数。使用 CPXaddrows 添加以下约束：

c'x = z*

将目标函数更改为其他目标；将单纯形迭代限制设置为 1（一）（或在 MIP 的情况下为解决方案限制 1）；然后反复优化问题。这个修改后的问题的每个可行解都是原始问题的最优解。此过程将为原始问题提供一些但不一定是全部的替代最佳解决方案。请注意，这种添加约束的方法也适用于具有二次目标的连续模型，而以零成本降低的固定非基本变量的方法不容易扩展到非线性目标。由于 CPLEX 求解凸二次规划，因此对二次目标的约束必须是不等式而不是等式，如上述线性目标的情况中所述。由于只有成本降低为 0（零）的非基本变量会在应用程序从一个备用最优解移到另一个时发生变化，所以您还可以通过使用例程 CPXgetdj 和 CPXgetpi 来识别非基本结构变量和非零松弛来枚举备用最优解降低了成本。然后，使用 CPXchgbds 将这些结构变量修复为其当前值，并使用 CPXchgsense 修复松弛变量。将单纯形迭代限制设置为 1（一）；像以前一样改变目标；您可以列举一些但不是全部的替代最佳解决方案。您还可以通过使用例程 CPXgetdj 和 CPXgetpi 来枚举替代最优解，以识别非基本结构变量和非零成本的松弛。然后，使用 CPXchgbds 将这些结构变量修复为其当前值，并使用 CPXchgsense 修复松弛变量。将单纯形迭代限制设置为 1（一）；像以前一样改变目标；您可以列举一些但不是全部的替代最佳解决方案。您还可以通过使用例程 CPXgetdj 和 CPXgetpi 来枚举替代最优解，以识别非基本结构变量和非零成本的松弛。然后，使用 CPXchgbds 将这些结构变量修复为其当前值，并使用 CPXchgsense 修复松弛变量。将单纯形迭代限制设置为 1（一）；像以前一样改变目标；您可以列举一些但不是全部的替代最佳解决方案。

另一种非常相似的方法是将一个小的随机向量添加到相关的目标函数系数（即“扰动”目标），解决问题并验证新顶点与旧顶点不同并且它给出与旧顶点相同的目标函数值（如果不是，则再次扰动并重复）。Paul Rubin在这篇文章中很好地描述了这种技术。

对于 MIP 问题CPLEX，提供了一个解决方案池，可以保存一定数量的已找到的解决方案，以及populate搜索更多解决方案的功能。这篇文章（同样由 Paul Rubin 撰写）解释了它是如何在 Java API 下工作的。

更新

跟进以下评论：

  1. 即使有其他解决方案，我也需要我的最佳解决方案来保持不变。我只希望在退化的情况下改变基础。

目标函数值将保持不变，因为我们添加了目标应等于其最佳值 ( c'x = z*) 的约束。当我在上面说“生成一个新的最优解”时，我指的是一组新的最优对偶值，即不同的最优对偶基。原始解决方案将保持不变（前提是原始问题是退化的并且原始问题没有多个最优解决方案）。

  1. 改变基础后，我想重新评估对偶变量。如果我添加 c'x = z* 作为约束，它会将我的所有对偶设置为 0。

所有对偶都等于零的事实听起来像是一个实现问题。您是否检查了生成的 LP 是否可行并且是否返回了有限最优解？另外，我不确定我是否理解上述语句的第一部分（在更改 ... 变量之后）。根据定义，更改（对偶）基是对对偶变量的重新评估。当问题是原始退化时（当前情况），存在多个对偶最优解，因此对偶空间中基的变化会导致相同的最优解值和相同的原始基（除非问题同时具有原始和双重退化）。

  1. 我想避免解决，因为这是我首先要避免的：我可以通过用扰动的 b 解决我的问题来直接计算影子价格。

这是真的，但在这种情况下，我们需要解决问题2 * n时间，其中n的大小是b：我们需要替换每个组件，b并且b - 1每次b + 1都解决。

我不知道有任何方法可以在不解决的情况下完成您正在寻找的工作。我找到了CPLEX 的主要开发人员Tobias Achterberg 的相关帖子，他基本上描述了相同的方法。此外，本文通过再次求解 LP，从最优对偶解中恢复最优原始解。如果您利用问题的网络流结构，可能无法解决，但这需要为该特定问题构建自定义算法。几年前，我为很多尺寸配方做过类似的事情，这确实需要一些努力。

我希望这有帮助！

于 2014-09-19T00:57:34.183 回答