Efficiently representing a set of sets
I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain.  Suppose we have sets $S_1,\dots,S_k$ over a universe $U$ containing $n$ items (so $S_i \subseteq U$).  A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set.  In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $[S] \in \{0,1\}^n$: $[S]_i=1$ if $S$ includes the $i$ element of $U$, otherwise not.  (This order is known in the BDD literature as a "variable ordering".)  Then define the language $L$ by $L=\{[S_1],[S_2],\dots,[S_k]\}$.  A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose.  The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD.  It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard.  Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances.  ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs.  ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.