I have the following combinatorial optimisation problem of which I think someone has probably solved it before. Has someone come across this problem before, maybe in a different setting than in the one I present it here (permutations, strings, trees, ...)?
Let $S$ be a discrete, finite set. Let $S_1, S_2, \ldots, S_k$ be subsets of $S$. Consider a linear order $R$ on $S$. We say $R$ represents $S_i$ if the elements of $S_i$ appear consecutively in $R$.
Given $S$ and $S_1, \ldots, S_k$, find a linear order $R$ of $S$ that maximises the number of subsets $S_i$ it represents.
I can solve the problem when $R$ can represent all subsets (with PQ-trees).
Example
Let $S = \{1, 2, 3, 4, 5\}$ and $S_1 = \{1, 2, 3\}$, $S_2 = \{3, 5\}$, $S_3 = \{2, 4\}$, $S_4 = \{1, 5\}$.
For $R = (2, 1, 3, 5, 4)$, we have that $S_1$ and $S_2$ are consecuitive in $R$ but $S_3$ and $S_4$ are not.
For $R' = (4, 2, 1, 3, 5)$, we have that $S_1$, $S_2$, and $S_3$ are consecuitive in $R'$ but $S_4$ is not. Note that we can actually not do better than $R'$, which is good for three of the four subsets.
