Random costs in combinatorial optimization

Collective Phase in Resource Competition in a Highly Diverse Ecosystem

Organisms shape their own environment, which in turn affects their survival. This feedback becomes especially important for communities containing a large number of species; however, few existing approaches allow studying this regime, except in simulations. Here, we use methods of statistical physics to analytically solve a classic ecological model of resource competition introduced by MacArthur in 1969. We show that the nonintuitive phenomenology of highly diverse ecosystems includes a phase where the environment constructed by the community becomes fully decoupled from the outside world.

Traveling salesman problem with a center

We study a traveling salesman problem where the path is optimized with a cost function that includes its length L as well as a certain measure C of its distance from the geometrical center of the graph. Using simulated annealing (SA) we show that such a problem has a transition point that separates two phases differing in the scaling behavior of L and C, in efficiency of SA, and in the shape of minimal paths.

Clustering analysis of the ground-state structure of the vertex-cover problem

Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdo s-Re nyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c<e , the system is replica symmetric, while for larger connectivities replica symmetry breaking occurs. This change coincides with a change of the typical running time of algorithms from polynomial to exponential. To understand the reasons for this behavior and to compare with the analytical results, we numerically analyze the structure of the solution landscape. For this purpose, we have also developed an algorithm, which allows the calculation of the backbone, without the need to enumerate all solutions. We study exact solutions found with a branch-and-bound algorithm as well as configurations obtained via a Monte Carlo simulation. We analyze the cluster structure of the solution landscape by direct clustering of the states, by analyzing the eigenvalue spectrum of correlation matrices and by using a hierarchical clustering method. All results are compatible with a change at c=e . For small connectivities, the solutions are collected in a finite small number of clusters, while the number of clusters diverges slowly with system size for larger connectivities and replica symmetry breaking, but not one-step replica symmetry breaking (1-RSB) occurs.

Dynamic phase diagram of the number partitioning problem

We study the dynamic phase diagram of a spin model associated with the number partitioning problem, as a function of temperature and of the fraction K/N of spins allowed to flip simultaneously. The case K=1 reproduces the activated behavior of Bouchaud's trap model, whereas the opposite limit K=N can be mapped onto the entropic trap model proposed by Barrat and Mézard. In the intermediate case 1<<K<<N , the dynamics corresponds to a modified version of the Barrat and Mézard model, which includes a slow (rather than instantaneous) decorrelation at each step. A transition from an activated regime to an entropic one is observed at temperature T(g) /2 in agreement with recent work on this model. Ergodicity breaking occurs for T< T(g) /2 in the thermodynamic limit, if K/N-->0 . In this temperature range, the model exhibits a nontrivial fluctuation-dissipation relation leading for K<<N to a single effective temperature equal to T(g) /2 . These results give insights into the relevance and limitations of the picture proposed by simple trap models.

Universality in the level statistics of disordered systems

Energy spectra of disordered systems share a common feature: If the entropy of the quenched disorder is larger than the entropy of the dynamical variables, the spectrum is locally that of a random energy model and the correlation between energy and configuration is lost. We demonstrate this effect for the Edwards-Anderson model, but we also discuss its universality.

Solving satisfiability problems by fluctuations: the dynamics of stochastic local search algorithms

Stochastic local search algorithms are frequently used to numerically solve hard combinatorial optimization or decision problems. We give numerical and approximate analytical descriptions of the dynamics of such algorithms applied to random satisfiability problems. We find two different dynamical regimes, depending on the number of constraints per variable: For low constraintness, the problems are solved efficiently, i.e., in linear time. For higher constraintness, the solution times become exponential. We observe that the dynamical behavior is characterized by a fast equilibration and fluctuations around this equilibrium. If the algorithm runs long enough, an exponentially rare fluctuation towards a solution appears.

Phase transition and landscape statistics of the number partitioning problem

The phase transition in the number partitioning problem (NPP), i.e., the transition from a region in the space of control parameters in which almost all instances have many solutions to a region in which almost all instances have no solution, is investigated by examining the energy landscape of this classic optimization problem. This is achieved by coding the information about the minimum energy paths connecting pairs of minima into a tree structure, termed a barrier tree, the leaves and internal nodes of which represent, respectively, the minima and the lowest energy saddles connecting those minima. Here we apply several measures of shape (balance and symmetry) as well as of branch lengths (barrier heights) to the barrier trees that result from the landscape of the NPP, aiming at identifying traces of the easy-hard transition. We find that it is not possible to tell the easy regime from the hard one by visual inspection of the trees or by measuring the barrier heights. Only the difficulty measure, given by the maximum value of the ratio between the barrier height and the energy surplus of local minima, succeeded in detecting traces of the phase transition in the tree. In addition, we show that the barrier trees associated with the NPP are very similar to random trees, contrasting dramatically with trees associated with the p spin-glass and random energy models. We also examine critically a recent conjecture on the equivalence between the NPP and a truncated random energy model.

Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random satisfiability problem, and its application to stop-and-restart resolutions

A large deviation analysis of the solving complexity of random 3-satisfiability instances slightly below threshold is presented. While finding a solution for such instances demands an exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. This exponentially small probability of easy resolutions is analytically calculated, and the corresponding exponent is shown to be smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some theoretical basis to heuristic stop-and-restart solving procedures, and suggests a natural cutoff (the size of the instance) for the restart.

Optimal combinations of imperfect objects

We consider how to make best use of imperfect objects, such as defective analog and digital components. We show that perfect, or near-perfect, devices can be constructed by taking combinations of such defects. Any remaining objects can be recycled efficiently. In addition to its practical applications, our "defect combination problem" provides a novel generalization of classical optimization problems.

Criticality of natural absorbing states

We study a recently introduced ladder model that undergoes a transition between an active and an infinitely degenerate absorbing phase. In some cases the critical behavior of the model is the same as that of the branching-annihilating random walk with N>/=2 species both with and without hard-core interaction. We show that certain static characteristics of the so-called natural absorbing states develop power-law singularities that signal the approach of the critical point. These results are also explained using random-walk arguments. In addition to that we show that when dynamics of our model is considered as a minimum-finding procedure, it has the best efficiency very close to the critical point.

Entropy-based analysis of the number partitioning problem

In this paper we apply the multicanonical method of statistical physics on the number partitioning problem (NPP). This problem is a basic NP-hard problem from computer science, and can be formulated as a spin-glass problem. We compute the spectral degeneracy, which gives us information about the number of solutions for a given cost E and cardinality difference m. We also study an extension of this problem for Q partitions. We show that a fundamental difference on the spectral degeneracy of the generalized (Q>2) NPP exists, which could explain why it is so difficult to find good solutions for this case.