Abstracts Engineering

Contributions to a New CBLS Backend for MiniZinc

by Maarten Lucas Flippo

MiniZinc is a language which enables the modelling of combinatorial optimisation and satisfaction problems independently from any particular problem solver and its technology. One technology for solving combinatorial optimisation and satisfaction problems is constraint-based local search (CBLS). The performance of a CBLS solver is dependent, amongst other factors, on its search procedure and on the shape of the invariant graph that is inferred from the model. We present the design for a new CBLS backend for MiniZinc. The strategy of encoding a model as an invariant graph is presented. Furthermore, the design of the search procedure, which uses simulated annealing as ameta heuristic, is laid out. Experiments show the backend can already produce high-quality solutions to relevant models in reasonable time, compared to existing CBLS backends for MiniZinc.