Solution-space structure of (some) optimization problems

Details Solution-space structure of (some) optimization problems Solution-space structure of (some) optimization problems

2007-11-25

arxiv.org/abs/0711.3912v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

10 pages, 5 figures, Fig. 4 in reduced quality to reduce size, Proceedings of the International Workshop on Statistical-Mechan

Scientific paper

10.1088/1742-6596/95/1/012011

We study numerically the cluster structure of random ensembles of two NP-hard optimization problems originating in computational complexity, the vertex-cover problem and the number partitioning problem. We use branch-and-bound type algorithms to obtain exact solutions of these problems for moderate system sizes. 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 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 to multiple nested levels of clusters. 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.

Affiliated with

Also associated with

No associations

Rating

Solution-space structure of (some) optimization problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solution-space structure of (some) optimization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solution-space structure of (some) optimization problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-512157