# Does this problem fall into any common problem definition…Knapsack maybe?

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.

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)

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.