2

你知道是否有办法改变已经解决的 Cplex 约束优化问题中的一些约束，并再次解决它，但结果尽可能接近以前的解决方案。

例子：

任务分配给不同的资源。资源 1 有任务 A、B 和 C，资源 2 有任务 D、E 和 F。

当我添加资源 3 时，我希望新分配类似于：

R1 = A & B
R2 = D & E
R3 = C & F

但 Cplex 可能会返回如下内容：

R1: F & E
R2: A & B 
R3: C & D

或任何其他可能与初始解决方案完全不同的组合。

我认为这个问题被称为动态约束满足问题。

我一直在做很多研究，但似乎没有一种简单的方法可以做到这一点。看起来我必须自己实现（没关系）。在那种情况下，你建议我应该如何解决这个问题？

谢谢

4

1 回答 1

2

这些问题的类别在运筹学中更普遍地称为分配问题。

很简单，我们在某些约束下将任务分配给资源。目标函数（goal）是最小化此类任务的成本。一组约束确保每个作业都分配给一个资源。

您当然可以使用 CPLEX（或任何 LP 求解器）来获得解决方案。特别是分配问题“更容易”，因为您甚至不需要调用Simplex。一种称为匈牙利方法的方法将产生最佳解决方案。

具体来说，在您的情况下，由于您希望保留大部分现有解决方案，您可以分配成本或权重以激励某些分配。例如，在您的问题中，如果您将A和B分配给R1的成本非常低，那么最终的解决方案将具有该成本，除非迫切需要更改该分配。

这是Assignment Problem的一个参考。

还可以在 Wikipedia 中查找The Hungarian Method，其中有一个非常易于访问的部分，称为外行的解释。完成此操作后，您还可以阅读 CPLEX 中的敏感性分析，其中您使用所谓的“热启动”来使用先前生成的解决方案。

于 2012-01-15T09:00:41.250 回答