Find the combination that minimizes a cost function

Hello everyone, I am facing a problem and I would be grateful to anyone that could help. The problem is the following:

Consider that we have a vector D = [D1;D2;D3;...;DN] and a set of time instances TI = {t1,t2,t3,...,tM}. Each element of vector D, Di, corresponds to a subset of TI. For example D1 could correspond to time instances {t1,t2,t3} and D2 to {t2,t4,t5}.

I would like to find the combination of elements of D that corresponds to all elements of TI, without any of these being taken into account more than once, and at the same time minimizes the cost function sum(Dj). Dj are elements of vector D and each one corresponds to a set of time instances.

Let me give an example. Let us consider a vector D = [15;10;5;2;35;15;25;25;25;30;45;5;1;40] and a set TI={5,10,15,20,25,30}. Each of D elements corresponds to {[5 15];[5 20];[5 25];[5 30];[5 15 20];[5 20 25];[5 15 30];[5 20 25 30];[10 15];[10 20];[10 25];[10 15 20];[10 15 20 25];[10 30]} respectively, e.g. D(1)=15 corresponds to time intances [5 15].

The solution that the procedure has to come up with is that the combination of D(4) and D(12), i.e. 2 and 1 respectively, has the minimum sum and correspond to all time instances.

I have to mention that the procedure has to be able to work with large vectors.

Thanks for every attempt to help!

[Jan]

What ist "large" exactly? It matters if you are talking about 50 elements or 500'000.

[ToLos Mil]

Let's say that large is at the order of hundreds of elements.

Answer 1

[ToLos Mil]

See the link below for a solution using bintprog function.

http://stackoverflow.com/questions/15205928/find-the-combination-that-minimizes-a-cost-function/15207017#15207017