2
$\begingroup$

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)

$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Rob, thank you for the help on the actual “formulation.” I don’t have a true OR background, but the concepts made a lot of sense to me. That is actually how I implemented the MILP but couldn’t describe to well with words, the use of the decision variables and then the what I call switching variables (T) $\endgroup$ – S moran May 10 at 15:59
  • $\begingroup$ Does this fall Into any know problem types that might have good heuristic approaches? $\endgroup$ – S moran May 10 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.