MOVED TO OR STACK
I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it fits the methods of some other common problems, where I may be able to apply some well known heuristics.
Given a set , $S$, of $n$ discrete items, $i$, and $k$ subsets, $M$, of $S$ $$ S :=\{i_1,i_2,i_3\dots,i_n\} $$ $$ M_{1,2,3,\dots k} \subseteq S $$
Choose exactly $X$ subsets $M$, such that $$X < k$$ to minimize the number of items $i$ that are in 2 or more of the $X$ subsets.
ADDT'L Notes
- There is no extra value if the items $i$ are selected 0 or 1 times, just less then 2
- Every item $i$ IS NOT required to be selected
- Each subset is predefined, and pseudo random
$$ ---- Below is just a different attempt at formulation---- $$
I tried to keep it more math definition oriented above, but the other way I simplified the problem is (using my some programming aspects):
1) I have a logical matrix , M ( i rows, j col) , where the rows represent the population and the columns represent the available subsets. 2) Goal is to optimize F, a column vector ( j , 1), that represents the choice of each subset (columns of M) to minimize the number of elements of M x F that are >= 2; 3) F is subject to you are required to choose exactly X subsets.
Need to define a column logical vector F (j rows, 1 columns) such that F has K true entries (representing the sub set choices) and the rest are false
i = 1e6; j = 150; X = 140
Set_Matrix = randi( [0 1], i , j );
Optimize F as to Minimize : sum(sum(Set_Matrix * F) >= 2) Where sum(F) == X (I.e pick 140 of the 150 subsets)