2

我有一个在 OPL 中实现的模型。我想用这个模型在java中实现本地搜索。我想用一些启发式方法初始化解决方案，并将这些初始解决方案提供给 cplex 根据模型找到更好的解决方案，但我也想将搜索限制在特定的邻域。关于如何做的任何想法？

另外，如何限制所有变量的范围？什么是最好的：在自己的 opl 或 java 甚至 C++ 中实现这些启发式和本地搜索？

提前致谢！

4

2 回答 2

1

这是几个问题。所以这里有一些指针和建议：

  1. 在 Cplex 中，您可以使用IloOplCplexVectors() Here's a good example in IBM's documentation of how to alter CPLEX's solution，为您的模型提供初始解决方案。

  2. 在 OPL 中，您可以执行相同的操作。您基本上为变量设置了一系列值，并将这些值交给 CPLEX。（见这个例子。）

  3. 将搜索限制在特定社区：在不了解详细信息的情况下，没有简单的方法可以做出回应。但是人们可以通过两种方式做到这一点：

    一个。改变目标以支持该“社区”并使其他区域没有吸引力。

    湾。添加从搜索空间中剔除其他社区的约束。

  4. 关于限制 OPL 中的变量范围，可以直接做：

    dvar int supply in minQty..maxQty;

或者对于整个决策变量数组，您可以执行以下操作：

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

希望这可以帮助您继续前进。

于 2013-08-22T05:46:27.980 回答
1

只是添加一些相关的观察：

Re 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。另一个变体是限制诸如汉明距离之类的东西（假设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# 等语言中创建如此多的数据结构。

于 2013-08-23T07:36:05.337 回答