Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSolution-space structure of (some) optimization problems
103
0
0.0
(
0
)
Added by
Alexander K. Hartmann
Publication date
2007
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
The solution-space structure of the 3-Satisfiability Problem (3-SAT) is studied as a function of the control parameter alpha (ratio of number of clauses to the number of variables) using numerical simulations. For this purpose, one has to sample the solution space with uniform weight. It is shown here that standard stochastic local-search (SLS) algorithms like ASAT and MCMCMC (also known as parallel tempering) exhibit a sampling bias. Nevertheless, unbiased samples of solutions can be obtained using the ballistic-networking approach, which is introduced here. It is a generalization of ballistic search methods and yields also a cluster structure of the solution space. As application, solutions of 3-SAT instances are generated using ASAT plus ballistic networking. The numerical results are compatible with a previous analytic prediction of a simple solution-space structure for small values of alpha and a transition to a clustered phase at alpha_c ~ 3.86, where the solution space breaks up into several non-negligible clusters. Furthermore, in the thermodynamic limit there are, for values of alpha close to the SATUNSAT transition alpha_s ~ 4.267, always clusters without any frozen variables. This may explain why some SLS algorithms are able to solve very large 3-SAT instances close to the SAT-UNSAT transition.
We consider disordered tight-binding models which Greens functions obey the self-consistent cavity equations . Based on these equations and the replica representation, we derive an analytical expression for the fractal dimension D_{1} that distinguishes between the extended ergodic, D_{1}=1, and extended non-ergodic (multifractal), 0<D_{1}<1 states. The latter corresponds to the solution with broken replica symmetry, while the former corresponds to the replica-symmetric solution. We prove the existence of the extended non-ergodic phase in a broad range of disorder strength and energy as well as existence of transition between the two extended phases. The results are applied to the systems with local tree structure (Bethe lattices) and to the systems with infinite connectivity (Rosenzweig-Poter random matrix theory). We obtain the phase diagram in the disorder-energy plain for the Bethe lattice and identify two insulating phases classified by the (one-step) replica symmetry breaking parameter. Finally we express the line of the Anderson localization transition, the stability limit of the non-ergodic extended phase and the line of the first order transitions between the two extended phases in terms of the Lyapunov exponents.
The conjugate gradient (CG) method, a standard and vital way of minimizing the energy of a variational state, is applied to solve several problems in Skyrmion physics. The single-Skyrmion profile optimizing the energy of a two-dimensional chiral magnet is found without relying on specific boundary conditions. The two-dimensional Skyrmion lattice and three-dimensional hedgehog crystal state is recovered with efficiency using the modified CG (p-GD) method. The p-GD method is proposed as a complement to the traditional Monte Carlo annealing method, which still gives better results for the ground state but at the far greater cost in computation time.
An optimization algorithm is presented which consists of cyclically heating and quenching by Metropolis and local search procedures, respectively. It works particularly well when it is applied to an archive of samples instead of to a single one. We demonstrate for the traveling salesman problem that this algorithm is far more efficient than usual simulated annealing; our implementation can compete concerning speed with recent, very fast genetic local search algorithms.
Fermi and kinetic energy are usually calculated in periodic boundary conditions model, which is not self-consistent for low-dimensional problems, where particles are confined. Thus for confined particles the potential box model was used self-consistently to calculate Fermi and kinetic energies in 3-, 2-, and 1-dimensional cases. This approach is much more logical and self-consistent. Then the conditions for neglecting dimensions, that is conditions under which the movement of particles in the box could be considered as 2- and 1- dimensional, were derived.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
