optimizing choosing best items from a collection

[Gijs Koot]

Hi, 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, use a different solver, maybe other ideas, to speed this up?

[Alastair Andrew]

Hi,

One thing you could try is being more strict about the cardinality of choices. If you want the top 10 results then add it an an equality constraint
```

constraint card(choices) = 10;

```

That'll reduce the potential search space by a decent chunk. 

AA

[Jip Dekker]

Since you are using a fixed (or limited) cardinality set, the standard decomposition might not work in your favour in this case. We recently experimented with different representations. We have some new decomposition methods that should work, but essentially changing the variable viewpoint as follows should do the trick:
include "strictly_increasing.mzn";

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

array[1..10] of var CANDIDATES: choices;
constraint strictly_increasing(choices);

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

Note that I here use Alastair's suggestion and force that 10 candidates are chosen. However, the model should work just as well with "var opt CANDIDATES" and allow a cardinality of less than 10.

Cheers,
Jip