如何提高用 MiniZinc 解决 Set Covering 问题的速度？

Question

最近我试图用 MiniZinc 解决 [Balas, E., & Ho, A. (1980)] 提出的集合覆盖问题实例。

我尝试了两种解决SCP41实例的方法或模型：

型号

(1)。 ILP 模型

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

(2)。带有代码、forall、数组等的 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（使用 mip/cbc 求解器为 0.6 秒）。