[Scip] Scip for combinatorial enumeration and probability

[David Ruescas]

Hello,

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.

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]

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.

Thanks again,

David

[1]
https://blog.agoravoting.com/index.php/2013/09/26/vote-inference-and-liquid-recurring-elections-example-solution/


On Mon, Sep 30, 2013 at 7:49 AM, Stefan Heinz <heinz at zib.de> wrote:

> Hi David,
>
> In the CP community there is research going on which uses your idea to
> find a good branching candidate. An example paper is
>
> http://dl.acm.org/citation.**cfm?id=1786734<http://dl.acm.org/citation.cfm?id=1786734>
>
> 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.
>
> 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.
>
> In case of SCIP the paper
>
> http://opus4.kobv.de/opus4-**zib/frontdoor/index/index/**docId/1063<http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1063>
>
> describes what SCIP is doing and contains some references to other tools
> which are capable of counting feasible solutions.
>
> Best Stefan
>
>
> On 09/29/2013 04:46 PM, Victor S. Miller wrote:
>
>> 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 ).
>>
>> Victor
>>
>> https://www.math.ucdavis.edu/~**latte/<https://www.math.ucdavis.edu/~latte/>
>>
>> Sent from my iPhone
>>
>>  On Sep 29, 2013, at 9:22, David Ruescas <fastness at gmail.com> wrote:
>>>
>>> Hello scip,
>>>
>>> I have a question which I'm not sure belongs on this list. If so, please
>>> let me know, apologies in advance.
>>>
>>> I'm wondering whether using scip's solution counting capability is a
>>> viable approach for calculating probabilities over integer values. Consider
>>> this simple example
>>>
>>> a + b = 25
>>> c + d = 34
>>>
>>> a + c = 23
>>> b + d = 12
>>>
>>> (numbers may be inconsistent, just made them up)
>>>
>>> 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.
>>>
>>> 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.
>>>
>>> Does this use of scip make sense? Any pointers to literature on this
>>> topic?
>>>
>>> Kind regards,
>>>
>>> David
>>> ______________________________**_________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/**mailman/listinfo/scip<http://listserv.zib.de/mailman/listinfo/scip>
>>>
>>
>>
>> ______________________________**_________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/**mailman/listinfo/scip<http://listserv.zib.de/mailman/listinfo/scip>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20130930/a3f941e3/attachment.html>