Consider $N$ sets $S_1,S_2,....,S_{N}$ of binary strings with don't-cares ($X$) with $|S_i| = n$ and the length of all strings is $m$.In my application, $N=1000$, $n=100$ and $m=500$.I have to find atleast one binary string with all set bits (either $1$ or $0$) that is compatible with at least one string of each set. Two strings are compatible if they are bit-wise similar. As we know $X$ bits are similar to both $0$ or $1$. For example, consider string $A=10XX0$ and string $B=X011X$. Here string $A$ and $B$ are compatible with each other. As we can see, due to the size of each string ($m=500$), it's impossible to find a solution with brute force (i.e. create all possible strings of length $m$ and compare each with all strings of all sets). So, I am looking for a reasonable heuristic to find the solution. 
Find a string that covers many sets of binary strings with don't-cares
algorithms;strings;heuristics;enumeration
Your problem is NP-hard.  It's basically a variant of SAT.  You shouldn't expect any algorithm that is provably efficient.  Instead, I recommend you use an off-the-shelf SAT solver; since your problem is basically SAT, that's probably about as good as you can do, without a lot of effort tuning for your particular scenario.NP-hardness: In particular, if every element of every set $S_i$ has exactly $m-1$ don't-cares (has only a single bit set to 0 or 1), then your problem becomes exactly $n$-CNF-SAT with $m$ variables and $N$ clauses.  We know that $n$-CNF-SAT is NP-hard; it follows that this special case of your problem is NP-hard, and thus your problem in general is NP-hard.Using a SAT solver: Introduce variables $x_1,\dots,x_m$ representing the string you're trying to find.  Then we obtain a formula of the form$$\Psi(x_1,\dots,x_m) = \bigwedge_{i=1}^N \bigvee_{j=1}^n \phi_{i,j}(x_1,\dots,x_m),$$where each $\phi_{i,j}$ is a conjunction of literals.  The goal is to find an assignment $x_1,\dots,x_m$ that makes $\Psi(x_1,\dots,x_m)$ true.You can formulate this as a SAT instance by applying the Tseitin transform.  In other words, introduce variables $y_{i,j}$, then add CNF clauses enforcing that $y_{i,j} = \phi_{i,j}(x_1,\dots,x_m)$ as well as CNF clauses $(y_{i,1} \lor \dots \lor y_{i,n})$ for all $i$.  The Tseitin transform tells you how to add the former clauses.  In particular, you add the clause $(\neg y_{i,j} \lor \neg x_k)$ if the $j$th element of $S_i$ has a 0 in its $k$th bit; add the clause $(\neg y_{i,j} \lor  x_l)$ if the $j$th element of $S_i$ has a 1 in its $l$th bit; and add the clause $(y_{ij} \lor x_k \lor \neg x_l \lor \dots)$ if the $j$th element of $S_i$ has a 0 in its $k$ bit and a 1 in its $l$th bit and so on.  Or, use a SAT front-end that will let you input arbitrary formulas and will do the Tseitin transform for you -- for instance, STP is a nice tool for that purpose.Then, let the off-the-shelf SAT solver look for a satisfying assignment for you.