[Scip] Scip for combinatorial enumeration and probability

[Benjamin Hiller]

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