  Max#SAT is an important problem with multiple applications in security and
program synthesis that is proven hard to solve. It is defined as: given a
parameterized quantifier-free propositional formula compute parameters such
that the number of models of the formula is maximal. As an extension, the
formula can include an existential prefix. We propose a CEGAR-based algorithm
and refinements thereof, based on either exact or approximate model counting,
and prove its correctness in both cases. Our experiments show that this
algorithm has much better effective complexity than the state of the art.
