Как я могу улучшить скорость решения проблемы Set Covering с MiniZinc?

Question

Недавно я пытался решить примеры проблем покрытия множеств, предложенные [Balas E., & Ho, A. (1980)] с помощью MiniZinc.

Я попробовал два способа или модели для решения экземпляра SCP41:

Модели

(1).Модель ILP

https://github.com/affernan/minizinctest/blob/master/scp_mzinc_lp.mzn

(2).Модель ILP с кодом, полем, массивом и т. Д. Я не уверен, что модели (1) == (2) https://github.com/affernan/minizinctest/blob/master/scp_mzinc_code.mzn

Для каждого запуска каждой модели на SCP41 MiniZinc никогда не заканчивает итерацию илидостижения оптимального.Я понимаю, что примеры и проблемы очень комбинаторные, но каким образом можно улучшить модели?

С уважением!

Answer 1

Обе эти модели решаются с помощью решателя MiniZinc mip в течение нескольких секунд (4,2 и 2,4 с на моей машине соответственно).Какой решатель ты пробовал?

Позже: вот немного более быстрая версия: http://www.hakank.org/minizinc/scp41.mzn (0,6 с использованием решателя mip / cbc).