Suppose I have an order batching problem (in a warehouse context) that I will like to solve with the aid of heuristics. In particular, I want to implement some well-known heuristics for warehouses with multiple cross aisles, such as the S-shape and Largest gap heuristics.
How can I implement them in MiniZinc? Is it possible to do so?
I looked up its documentation, but I could only find MiniSearch, which is a language for specifying meta-search in a MiniZinc model. (http://www.minizinc.org/minisearch/documentation.html)
Some insight into this will be deeply appreciated.
The answer to your question heavily depends on the nature of your heuristic. From the MiniZinc aspect I would identify three kinds of heuristics:
There is no straightforward MiniZinc-way of dealing with heuristics and you might need some creativity to implement your heuristic in a useable way. Here are some pointers to possible solutions:
In case you are dealing with a solving heuristics, you might not need to do any work; it already give you an solution. However, if you want to verify the solution or ensure an optimal solution, then you can consider running the model with the solution or using the solution as a warm start (respectively). (You could even implement the heuristic as a FlatZinc solver if it's broad enough, but consider the time investment vs. it's usability.)
In the other two cases the well known solution is to pre-compute the heuristics and include them within the model data. In case of a search heuristic it might be possible to compute the order in which the variables should be searched. You can then use this order in the input_order search heuristic. For a partial heuristic it is possible to precompute the partial model and include this directly in the model. This is often too constraining for the problem. Instead if you can compute multiple partial solutions, these can be included as a table constraint.
The previous solutions would only be possible if the heuristic algorithm does not depend on the domains of the variables within the search. When they do, we generally talk about "meta-search". This is were implementations like MiniSearch come in. In MiniSearch you can for example reflect on the last solution or last assignment and base new search behaviour on those values. This allows these more dynamic heuristics to be implemented.
Even MiniSearch does not generally run at every node. So in some situations you might not be able to use your heuristic in MiniZinc directly. An option in that case would be to add your heuristic to a FlatZinc solver and then call it using an designated annotation.