optimization - Cplex/OPL 本地搜索

Question

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

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

提前致谢!

Answer 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 个。另一种变体是限制汉明距离等内容(假设这里的变量都是二进制的):

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# 等语言创建如此多的数据结构。