2
$\begingroup$

I have a simple problem that doesn't perform well at the moment. I have a set of ~1000 candidates, from which I want to choose ~10 optimal candidates. They all have a score, and the optimal subset is clearly the ten candidates with the best score. This takes currently longer than twenty minutes to complete using this simple MiniZinc model.

enum CANDIDATES;
array [CANDIDATES] of float: scores;

var set of CANDIDATES: choices;

constraint card(choices) < 10;

solve maximize sum(c in choices)(scores[c]);

I understand it would be easy to solve this in another way, but I have additional constraints that make a general optimization approach preferable. Is there a way to code this up more efficiently?

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you specify the additional constraints? $\endgroup$
    – Kuifje
    Commented May 13 at 8:55
  • $\begingroup$ And do you absolutely need to use minizinc? $\endgroup$
    – Kuifje
    Commented May 13 at 8:55
  • $\begingroup$ Thanks for the questions. No I don't have any specific requirements on software but open source would be good. Other requirements are that the candidates are spread out well. There's a number of locations that need to be covered, preferably by a closeby candidate. The final solution should take into account the individual scores and the coverage of the target locations. $\endgroup$
    – Gijs
    Commented May 13 at 9:17
  • 1
    $\begingroup$ I suggest using PuLP (which automatically calls open source CBC). Please edit your question to specify the additional constraints, the community will help you model them. $\endgroup$
    – Kuifje
    Commented May 13 at 9:33
  • $\begingroup$ Thanks for the suggestion. Using a different solver made a big difference indeed, see the accepted answer, switching to HiGHS is very quick, but I'll try out PuLP later. $\endgroup$
    – Gijs
    Commented May 13 at 11:02

1 Answer 1

Reset to default
3
$\begingroup$

Minizinc supports MIP solvers, which are likely better than CP solvers when floats are used. When using HiGHS with random data (1000 scores), I see:

%%%mzn-stat: nodes=1
%%%mzn-stat: objective=8.94901188
%%%mzn-stat: objectiveBound=8.94901188
%%%mzn-stat: solveTime=0.034

Looks like I am doing much better than you are.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank, this works perfectly, I hadn't realized there would be such a big difference. $\endgroup$
    – Gijs
    Commented May 13 at 11:00
  • $\begingroup$ Minizinc supporting all these solvers is not just waste of effort. $\endgroup$
    – Erwin Kalvelagen
    Commented May 13 at 15:02
  • $\begingroup$ It is not! I did run into problems further down, when adding a more complicated constraint, the HiGHS solver wasn't able to translate these into the correct formulations. Maybe I'll make a follow-up question on it. For that part the Gecode solver works fast enough, and for this part of the problem the HiGHS solver worked fast enough. When combining the two types of constraints, I wasn't able to make it work fast enough for the problem. $\endgroup$
    – Gijs
    Commented May 14 at 11:06
  • $\begingroup$ Do better modeling! Build a proper MIP model or a proper CP model. $\endgroup$
    – Erwin Kalvelagen
    Commented May 14 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.