[Scip] Scip for combinatorial enumeration and probability

[David Ruescas]

Dear Benjamin,

Thank you for your comment.

I did not intend to generate _different_ solutions (after all, these are
fixed by the constraints) only to randomly alter _the order_ in which they
are enumerated. By doing this, one could enumerate eg the first 1000
solutions (when the space is much much larger) as a subsample. If the
ordering is sufficiently random, sampling could in theory allow estimations
when it is infeasible to enumerate the entire solution space.

I have tried to play around with this parameter, and the first subset of
solutions presented are indeed different. although I admittedly do not know
if the randomness involved is sound for sampling purposes.

Kind regards,

David


On Mon, Sep 30, 2013 at 10:05 PM, Benjamin Hiller <hiller at zib.de> wrote:

> Dear David,
>
> Am 30.09.2013 21:37, schrieb David Ruescas:
>
>  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.
>>
>
> I'm afraid that this will not work as expected. If I am not mistaken,
> misc/permutationseed is used to change the problem model (ie order of
> constraints), but introduces no real randomness apart from affecting
> certain tie-breaking situations. It might help to generate different
> optimal solutions with the same objective value, though.
>
> In order to find different solutions, you can probaly use a randomized
> objective function. But be warned that the solutions found this way will
> certainly not be uniformly distributed. Thus you cannot compute any
> reasonable probability estimates from the results since you do not know the
> probability of each solution.
>
> Best regards,
>
> Benjamin
> --
> Benjamin Hiller                                           hiller at zib.de
> Abteilung Optimierung                            phone +49 30 84185-406
> Leiter Arbeitsgruppe Energie
>
> Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
> Takustraße 7
> 14195 Berlin
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20130930/2799ca34/attachment.html>