MiniZinc :如何实现自定义搜索启发式？(用Gecode)

Question

对于完整的上下文，我的目标是实现一个“代理”，它试图以在线的方式从给定的池中学习最好的启发式(这意味着学习和解决过程同时进行)。本质上，搜索策略将基于重新启动:求解者应该能够在每次重新启动时根据搜索过程中积累的观察在搜索启发式之间切换。以下是以前关于这一主题的一些著作：

https://www.ijcai.org/proceedings/2022/258

https://drops.dagstuhl.de/opus/volltexte/2022/16661/

我认为这不能在MiniZinc中直接实现，必须在求解器(例如，Gecode)中直接实现。我对FlatZinc、解决程序以及两个接口是如何操作的知之甚少。事实上，我来自数学背景，一般没有多少编程经验。我可以看到，MiniZinc和Gecode参考手册都有很大的细节，但由于我似乎无法掌握基本知识，它们实际上使我比以前更加困惑。

到目前为止，我已经下载了Gecode源代码，但是即使我成功地实现了我的自定义启发式(这是一个很大的if)，我也不知道接下来的步骤是什么。我如何能够在MiniZinc中使用它呢？我真的很感激一些通用的指示(记住我没有太多的编程经验)！

Answer 1

MiniZinc中的搜索启发式通常通过搜索注释进行管理。

当求解器实现自定义搜索启发式时，它通常会添加一个求解器特定的注释。关于Gecode的示例可以在gecode.mzn文件中找到。然后，例如，要使用“放松和重构”(随机LNS)搜索启发式，可以包含Gecode声明，并将其用作普通搜索启发式：

include "gecode.mzn";
array[1..4] of var int: x;
solve ::relax_and_reconstruct(x, 90) maximize sum(x);

正如您描述的搜索启发式，relax_and_reconstruct依赖于重新启动。因此，需要使用重新启动标志来指示求解程序如何(以及何时)重新启动：--restart-base、--restart、--restart-scale、--restart-limit。

在Gecode中实现自定义搜索启发式可能很棘手，但是每加仑英里应该提供一个全面的指导。创建了新的搜索启发式之后，就可以将其添加到FlatZinc处理这里中，以将其添加到创建的实例中。(并将其添加到前面提到的gecode.mzn文件中，使其在MiniZinc中可用。