Search code examples
minizinc

How can I improve the speed of solution of Set Covering problem with MiniZinc?

Recently I trying to solve a Set Covering Problem Instances proposed by [Balas, E., & Ho, A. (1980)] with MiniZinc.

I tried two ways or models for solving SCP41 instance:

Models

(1). ILP model

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

(2). ILP model with code, forall, array, etc.. I'm not sure if models (1)==(2) https://github.com/affernan/minizinctest/blob/master/scp_mzinc_code.mzn

For each run of each model on SCP41, MiniZinc never finish iterating or reaching the optimum. I understand that the instances and the problem are very combinatorial, but in what way can the models be improved?

regards!

Solution

  • Both these models are solved by MiniZinc's mip solver within seconds (4.2s and 2.4s respectively on my machine). What solver did you try?

    Later: Here's a slightly faster version: http://www.hakank.org/minizinc/scp41.mzn (0.6s using the mip/cbc solver).