<div dir="ltr"><div>David, Another thing that you should look at is the book "Computing the Continuous Discretely: Integer Point Enumeration in Polyhedra" by Beck and Robins, in which they also discuss algorithms for sampling.<br>
<br></div>Victor<br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Sep 30, 2013 at 3:37 PM, David Ruescas <span dir="ltr"><<a href="mailto:fastness@gmail.com" target="_blank">fastness@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hello,<div><br></div><div>Thank you very much Victor and Stefan for your suggestions. I will be trying out Latte and will have a look at the papers to find more tools.</div>
<div><br></div><div>For your information, the underlying problem I am considering is related to privacy in secure liquid democracy elections. You can find a simple description of the problem in the link I provide below[1]</div>



<div><br></div><div>Another idea I will be trying with Scip is that of solution sampling for probability estimation. Using scip's misc/permutationseed parameter one could perhaps generate solutions randomly, and then sample these solutions to estimate the probability of the variables taking some values. This could be useful if the solution space is very dense and the solution count explodes.</div>



<div><br></div><div>Thanks again,</div><div><br></div><div>David</div><div><br></div><div>[1] <a href="https://blog.agoravoting.com/index.php/2013/09/26/vote-inference-and-liquid-recurring-elections-example-solution/" target="_blank">https://blog.agoravoting.com/index.php/2013/09/26/vote-inference-and-liquid-recurring-elections-example-solution/</a></div>

</div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Sep 30, 2013 at 7:49 AM, Stefan Heinz <span dir="ltr"><<a href="mailto:heinz@zib.de" target="_blank">heinz@zib.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi David,<br>
<br>
In the CP community there is research going on which uses your idea to find a good branching candidate. An example paper is<br>
<br>
<a href="http://dl.acm.org/citation.cfm?id=1786734" target="_blank">http://dl.acm.org/citation.<u></u>cfm?id=1786734</a><br>
<br>
As far as I know they usually look at a single constraint for computing the solution density. The main reason for that is that they need to be quick.<br>
<br>
In case of counting feasible solutions there are a view software packages available. SCIP and Latte are just two examples. In general it its hard to predict how good these methods are for particular problems. In would recommend to try it out.<br>


<br>
In case of SCIP the paper<br>
<br>
<a href="http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1063" target="_blank">http://opus4.kobv.de/opus4-<u></u>zib/frontdoor/index/index/<u></u>docId/1063</a><br>
<br>
describes what SCIP is doing and contains some references to other tools which are capable of counting feasible solutions.<br>
<br>
Best Stefan<div><div><br>
<br>
On 09/29/2013 04:46 PM, Victor S. Miller wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I recommend looking at Latte, which implements a sophisticated algorithm of Barvinok to count solutions, and even to integrate a function over the solutions (i.e. Take a weighted sum ).<br>
<br>
Victor<br>
<br>
<a href="https://www.math.ucdavis.edu/~latte/" target="_blank">https://www.math.ucdavis.edu/~<u></u>latte/</a><br>
<br>
Sent from my iPhone<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On Sep 29, 2013, at 9:22, David Ruescas <<a href="mailto:fastness@gmail.com" target="_blank">fastness@gmail.com</a>> wrote:<br>
<br>
Hello scip,<br>
<br>
I have a question which I'm not sure belongs on this list. If so, please let me know, apologies in advance.<br>
<br>
I'm wondering whether using scip's solution counting capability is a viable approach for calculating probabilities over integer values. Consider this simple example<br>
<br>
a + b = 25<br>
c + d = 34<br>
<br>
a + c = 23<br>
b + d = 12<br>
<br>
(numbers may be inconsistent, just made them up)<br>
<br>
The question is, given the above constraints, what is the probability that a (or b,c,d) is equal to some number? In this simple example, it would be trivial to calculate this directly. But if the number of constraints is much larger the problem becomes more complex.<br>


<br>
In such a scenario, one could in theory use scip to count the number of solutions overall, and then count the fraction of those that satisfy additional constraints (eg a = 10), hence obtaining a probability.<br>
<br>
Does this use of scip make sense? Any pointers to literature on this topic?<br>
<br>
Kind regards,<br>
<br>
David<br>
______________________________<u></u>_________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/<u></u>mailman/listinfo/scip</a><br>
</blockquote>
<br>
<br>
______________________________<u></u>_________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
<a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/<u></u>mailman/listinfo/scip</a><br>
</blockquote>
<br>
</div></div></blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
<a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a><br>
<br></blockquote></div><br></div>