Does this problem fall into any common problem definition....Knapsack maybe?

Question

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

1. There is no extra value if the items $i$ are selected 0 or 1 times, just less then 2
2. Every item $i$ IS NOT required to be selected
3. 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)

Answer 1

Here is a MILP formulation, in case you did something different. Let binary variable $F_j$ indicate whether subset $j$ is chosen. Let binary variable $T_i$ indicate whether item $i$ appears in two or more of the chosen subsets. The problem is to minimize $\sum_i T_i$ subject to: \begin{align} \sum_j F_j &= 140 \tag1 \\ \sum_j M_{i,j} F_j - 1 &\le 149 T_i &&\text{for all $i$} \tag2 \end{align} Constraint $(1)$ is the cardinality constraint. Constraint $(2)$ enforces $\sum_j M_{i,j} F_j \ge 2 \implies T_i = 1$. If most of these constraints are naturally satisfied anyway, you could generate them dynamically only if they are violated.