Find the combination that minimizes a cost function

Question

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 instance [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!

Answer 1

The binary weight vector x places a weight on each D_i.

Let f=[D1;D2;...;DN].

Column j of A, A_j is a binary vector.

A_jk is 1 if D_j corresponds to Tk, else is zero.

The problem is:

min f^T*x  s.t.  A*x=1;

Then use bintprog to solve.

x = bintprog(f,[],[],A,ones(M,1))