MiniZinc : how to implement custom search heuristics? (in Gecode)

Question

For full context, my goal is to implement an "agent" that attempts to learn the best heuristic from a given pool in an online fashion (meaning that the learning and the solving procedures are done simultaneously). Essentially, the search strategy will be based on restarts : the solver should be able to switch between search heuristics at every restart based on observations accumulated during the search. Here are some previous works on the subject :

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

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

I believe that this cannot be done directly in MiniZinc and must be implemented directly in a solver (Gecode for example). I know very little about FlatZinc, solvers, and how the two interface. In truth, I come from a mathematical background and don't have much experience with programming in general. I can see that both MiniZinc and Gecode reference manuals go into great details, but since I can't seem to grasp the basics, they actually left me more confused than before.

So far I have downloaded Gecode source code, but even if I managed to implement my custom heuristic (which is a big if), I'm not sure what the next steps would be. How would I be able to use it in MiniZinc ? I would really appreciate some general indications (keeping in mind I don't have much programming experience)!

Answer 1

Search heuristics in MiniZinc are generally managed through search annotation.

When a solver implements a custom search heuristic, it generally adds a solver specific annotation. Examples for Gecode can be found in the gecode.mzn file. Then to, for example, use the "relax and reconstruct" (random LNS) search heuristic, you can include the Gecode declarations and use it as a normal search heuristic:

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

Like you described search heuristic, relax_and_reconstruct depends on restarts. As such, it would require you to use the restart flags to instruct the solver how (and when) to restart: --restart-base, --restart, --restart-scale, --restart-limit.

Implementing a custom search heuristic in Gecode can be tricky, but the MPG should provide a comprehensive guide. When you've created your new search heuristic, then you can add it to the FlatZinc processing here to add it to the created instance. (And add it to the earlier mentioned gecode.mzn file to make it available in MiniZinc.