The paper deals with the problem of counting the number of optimal solutions in weighted CSPs. In order to solve it without requiring to enumerate these solutions, they map the cost functions into pairs (cost,count) and therefore reformulate the optimization problem within Semiring (R^2,x,+). They show how to adapt bucket elimination and AND/OR Branch and Bound to this semiring. Finally, some experiments highlight the effectiveness of the method. Although optimization in semirings is not novel and the formulation provided by the authors is not very surprising, the methodology is interesting by itself. The experiments are convincing on the set of algorithms compared. However, there exist in the literature other methods whose purpose is specifically to count models, e.g., the weighted model counting algorithm used by Chavira and Darwiche, but also sum-product networks in which MPE-like queries can be computed efficiently. Why don't the authors compare their algorithms against them in the experimental section?

The authors deal with a new problem that extends existing problems in a natural way, and present new solutions that extend existing solutions in a natural way; thus in some ways the paper is not very original, but it must be noted that the problem #opt has some surprising properties that make the whole endeavor quite interesting. As for the contribution, it is a valuable piece with new algorithms that have good performance. I really take issue with the emphasis on semirings; I cannot see how this helps the whole effort. Are semirings bringing new insights here? Or are they just more general so that the algorithm applies to other problems? Why does it make a difference to state results this way? Concerning the significance, the results do address and solve a new problem, but I think the authors should perhaps work a bit harder in explaining why this problem is significant in practice. This is a point that is left a bit weak. Concerning the text: - Instead of "[6] introduced...", better "Ref. [6] introduced..." (and similar expressions). - The fonts for Algorithm 1/2 are **very** small... please increase them. - Also Figure 3 is really too small. - Page 7, line 300: "were [by] guided by". - References: "fortran" should be "Fortran".

I have not much to say about this work for it is really good. The only sad thing is, that the authors ignore some classic results on this topic, like: "Finding the M Most Probable Configurations Using Loopy Belief Propagation", Chen Yanover and Yair Weiss, NIPS 2003