multiobjective solver

[Francesco Tonin]

Hi everyone!
I'm doing a project on multiobjective solver in minizinc, focused on the pareto optimization.

I was wondering if anyone had some tips for me, thank you.

[Jip Dekker]

I've worked on implementation of Pareto optimization in the past. Generally our approach has been to add a constraint whenever you find a solution that forces at least one of the objective to improve for the next solution. This means that new solutions found might still dominate the previous solutions, but a simple post-processing should make this easy to resolve.

To implement this using current MiniZinc (and with current solvers). The simplest method is to use the meta-heuristic capability in MiniZinc Python: https://python.minizinc.dev/en/develop/advanced_usage.html#defining-meta-heuristics

Alternatively, the "on restart" based meta search is included as an experimental feature in the current MiniZinc infrastructure. This feature is supported by the Chuffed and Gecode solvers. I've described in my PhD thesis how you can use these features to implement Pareto optimizaton (see section 5.2.4: https://bridges.monash.edu/articles/thesis/A_Modern_Architecture_for_Constraint_Modelling_Languages/16968229

For future versions of MiniZinc it would be interesting to have direct support for modelling multi-objective problems in MiniZinc, such as Pareto and lexicographic optimization. My vision would then be that solver would be allowed to support these features natively, but use these existing alternatives as a fallback.

[Jip Dekker]

I've created an example of implementing Pareto optimization using MiniZinc Python in the following Gist: https://gist.github.com/Dekker1/900f1c5cb739d5985f4fff024b225103

[Francesco Tonin]

Thank you so much!