|
Résumé |
We study numerically the solution-space clustering properties of
random ensembles of three models of disordered glassy problems.
Namely we investigate the vertex-cover
problem, the number-partitioning problem (both are optimization problems)
and a one-dimensional Ising spin glass with tunable long-range interaction.
We use branch-and-bound type algorithms to obtain exact
solutions of these problems for moderate system sizes as
well as parallel tempering simulations (MC3).
Using two methods, direct neighborhood-based clustering and
hierarchical clustering, we investigate the structure of the solution
space. The main result is that the correspondence between
solution-space structure and the phase diagrams of the problems is not
unique. Namely, for vertex cover we observe a drastic change of the
solution space from large single clusters (in the replica-symmetric
phase, as obtained by previous analytical studies) to multiple
nested levels of clusters (in the replica-symmetry broken phase). In
contrast, for the number-partitioning problem, the phase space looks
always very simple, similar to a random distribution of the
lowest-energy configurations. This holds in the ``easy''/solvable
phase as well as in the ``hard''/unsolvable phase. Finally, for
the long-range spin glass, we observe a complicated clustering structure,
as well as ultrametricity, close to the point where the model
attains a trivial behavior (and where it is believed to be
equivalent to standard one and two-dimensional short-range spin glasses) |
