Algorithm to find best combination

I am looking for a algorithm that will help me to choose the combinations with the minimum sum. Let's say I have differents combinations of numbers and for each of them I have a cost. I have to choose the combinations that will cover all the numbers but with the minimum cost. For example

Combinations with numbers 2 to 7

Combination        Cost
________________   _______
2    3    4    5   10.9084
2    3    4    6   10.3335
2    3    4    7    8.8927
2    3    5    6   11.3927
2    3    5    7   11.4411
2    3    6    7   11.5541
(...)

I was looking for hours for severals algorith, but no one is doing exactly what I want. Can someone direct my research to the right algorithm?

Thanks.

Yannick

Answer 1

[Walter Roberson]

For up to about 11 items in the set, then usually the fastest approach is to generate all the combinations and run the calculation in vectorized form over all of them, choosing the one that gives the best result.

Once you get to roughly 12 then the number of possibilities starts becoming large enough that more complex approaches start winning.

Using combinations of integers is a form of integer programming. MATLAB used to have a separate integer-only programming function, but it was replaced by "mixed integer" routines, which are routines which can take a mix of integer constraints and continuous bound constraints. https://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-algorithms.html

The difficulty with intlinprog() is that it has real way to say that only combinations (or permutations) are to be used, as opposed to simply integers within a range but which might be repeated. But if your function works with ordered inputs, then it is possible to program it by using the A, b, matrices, where for each adjacent pair of values you would configure weights 1 for x(K) and -1 for x(K+1) and have -1 in the corresponding element of b: x(K)-x(K+1) <= -1 is true for integer x only if the values are sorted in increasing order.