[Scip] Scip for combinatorial enumeration and probability

[Victor Miller]

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.

Victor


On Mon, Sep 30, 2013 at 3:37 PM, David Ruescas <fastness at gmail.com> wrote:

> 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>
>>>
>>
>>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20130930/21506dc4/attachment.html>