Cplex/OPL本地搜索

Question

我有一个在OPL中实现的模型。我想使用这个模型在java中实现本地搜索。我想用一些启发式方法初始化解，并给出这些初始解，以便在模型的基础上找到更好的解，但我也想将搜索限制在一个特定的邻域。知道怎么做吗？

此外，如何限制所有变量的范围？最好的方法是:在自己的opl、java甚至C++中实现这些启发式和本地搜索？

提前感谢！

Answer 1

这是几个问题。以下是一些建议和建议：

1. 在Cplex中，通过使用IloOplCplexVectors()，您可以为模型提供一个初始解决方案--以下是如何更改CPLEX解决方案的IBM的好例子文档。
2. 在OPL中，您也可以这样做。基本上，您为变量设置了一系列值，并将这些值交给CPLEX。(参见此示例.)
3. 将搜索限制在一个特定的邻居上：在不知道细节的情况下没有简单的响应方式。但是，人们有两种方法可以做到这一点： 改变目标，以利于“邻里”，并使其他领域失去吸引力。 ( b )增加限制，从搜索空间中排除其他社区。
4. 关于限制OPL中变量的范围，您可以直接这样做： dvar供应；minQty..maxQty；

或者，对于整个决策变量数组，您可以按照以下方式进行如下操作：

range CreditsAllowed = 3..12;
dvar int credits[student] in CreditsAllowed;

希望这能帮你继续前进。

Answer 2

我只想补充一些相关的意见：

Ram的第3点:我们在方法b方面取得了很大的成功，特别是简单地添加了一些约束，将一些变量修复到一个已知解决方案的值中，然后再对问题中的其他变量进行重新求解。更一般地，您可以添加约束来限制与以前的解决方案类似的值，例如：

var >= previousValue - 1
var <= previousValue + 2

当然，这对二进制变量没有任何用处，但是对于一般的整数变量或连续变量来说可以工作得很好。这种方法可以推广到变量集合：

sum(i in indexSet) var[i] >= (sum(i in indexSet) value[i])) - 2
sum(i in indexSet) var[i] <= (sum(i in indexSet) value[i])) + 2

这个可以对二进制变量集很好地工作。对于一个由100个二进制变量组成的数组(其中可能有10个变量的值为1)，我们将寻找至少8个变量的值为1，但不超过12个的解决方案。另一个变量是限制类似Hamming距离的值(假设vars在这里都是二进制的)：

dvar int changed[indexSet] in 0..1;
forall(i in indexSet)
  if (previousValue[i] <= 0.5)
    changed[i] == (var[i] >= 0.5) // was zero before
  else
    changed[i] == (var[i] <= 0.5) // was one before

sum(i in indexSet) changed[i] <= 2;

这里我们要说的是，在一个包含100个二进制变量的数组中，最多只能允许两个变量的值与以前的解决方案不同。

当然，你可以把这些想法结合起来。例如，在以前的值中添加一些简单的约束来修复很大一部分问题，同时留下一些其他变量需要重新解决，然后在剩余的一些自由变量上添加约束，以限制新的解决方案接近上一种解决方案。当然，您会注意到，随着我们试图变得更聪明，这些方案的实现和维护变得更加复杂。

要想让本地搜索工作顺利进行，你需要仔细考虑如何建造当地的街区--太小了，而你所寻求的改进机会也太少，而如果它们太大，则需要很长时间才能解决，因此你就不会有那么多的改进步骤。

一个相关的问题是，每个社区都需要合理地在内部建立联系。我们做了一些实验，我们在一个模型中固定了可能99%的变量的值，并对剩下的1%进行了求解。当1%聚类在模型中(例如，所有资源子集的分配变量)时，我们得到了很好的结果，而比较而言，我们从模型的任意位置随机选择1%的变量是没有结果的。

一个经常被忽视的想法是将这些相同的限制倒置到模型上，以此迫使解决方案中的一些变化达到一定程度的多样化。因此，您可以添加一个约束，强制某个特定值与前一个解决方案的不同，或者确保在100个二进制变量数组中，至少有两个与前一个解决方案不同的值。我们用这种方法得到了一种混合数学模型的禁忌搜索。

最后，我们主要在C++和C#中完成了这一点，但是它在Java中会非常好地工作。不是从OPL那里试过太多，但也应该是好的。对我们来说，关键是能够遍历问题结构，并使用问题知识来选择我们冻结或放松的变量集--我们只是发现用C#这样的语言编写代码变得更容易、更快，但是建模内容更难编写和维护。我们可能有点“老派”，喜欢对我们正在做的事情进行详细的细粒度控制，并发现我们需要在OPL中创建更多的数组和索引集来实现我们想要的结果，而我们可以通过更智能的循环等来实现同样的效果，而不需要在像C#这样的语言中创建这么多的数据结构。