[Scip] Scip for combinatorial enumeration and probability

[Stefan Heinz]

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

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

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/
>
> 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
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip