Phase transition and landscape statistics of the number partitioning problem

Author(s)

Stadler‚ P.F. ; Hordijk‚ W. ; Fontanari‚ J.F.

• Document type: Journal article
• Source: Physical Review E; v. 67, n. 5, p. 056701, 2003.

Abstract

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. (AU)

• FAPESP's process: 99/09644-9 - Theoretical Molecular Evolution
• Grantee: José Fernando Fontanari
• Support Opportunities: Research Projects - Thematic Grants