Solution-space structure of (some) optimization problems

Abstract

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.

10 pages, 5 figures, Fig. 4 in reduced quality to reduce size, Proceedings of the International Workshop on Statistical-Mechanical Informatics 2007, Kyoto (Japan) September 16-19, 2007

References in corpus (21)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Phase Transition in the Number Partitioning Problem
• Coloring random graphs
• The Entropy of the K-Satisfiability Problem
• A variational description of the ground state structure in random satisfiability problems
• Core percolation in random graphs: a critical phenomena analysis
• Random Costs in Combinatorial Optimization
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
• Number partitioning as random energy model
• Statistical mechanics of the vertex-cover problem
• Spin Domains Generate Hierarchical Ground State Structure in J=+/-1 Spin Glasses
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Lack of Ultrametricity in the Low-Temperature phase of 3D Ising Spin Glasses
• The nature of ergodicity breaking in Ising spin glasses as revealed by correlation function spectral properties
• Extensive eigenvalues in spin-spin correlations: a tool for counting pure states in Ising spin glasses
• On the Tail of the Overlap Probability Distribution in the Sherrington--Kirkpatrick Model
• A Quantitative Clustering Approach to Ultrametricity in Spin Glasses

Cited by in corpus (4)

• Core percolation on complex networks
• Numerical Solution-Space Analysis of Satisfiability Problems
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Statistical mechanical models of integer factorization problem