Statistical mechanics of combinatorial optimization problems with site disorder

We study the statistical mechanics of a class of problems whose phase space is the set of permutations of an ensemble of quenched random positions. Specific examples analyzed are the finite-temperature traveling salesman problem on several different domains and various problems in one dimension such as the so-called descent problem. We first motivate our method by analyzing these problems using the annealed approximation. Then in the limit of a large number of points we develop a formalism to carry out the quenched calculation. This formalism does not require the replica method, and its predictions are found to agree with Monte Carlo simulations. In addition our method reproduces an exact mathematical result for the maximum traveling salesman problem in two dimensions and suggests its generalization to higher dimensions. The general approach may provide an alternative method to study certain systems with quenched disorder.

Figure 1

Ring polymer on a two-dimensional substrate where each monomer (solid circles) is attached to an impurity (crosses).

Figure 2

Expectation value for the fluctuations in winding number per site, $⟨\overline{W^2}⟩∕N$, for the one-dimensional TSP on the ring domain as a function of $\beta$ (dotted line) compared with the Monte Carlo simulations (crosses). Negative $\beta$ corresponds to the maximum TSP.

Figure 3

Theoretical prediction for the average energy $ϵ$ for the two-dimensional quenched polymer model as a function of $\beta$ (solid line) compared with the Monte Carlo simulations (solid circles). Negative $\beta$ corresponds to the maximal problem. Error bars based on 20 realizations of the quenched points are smaller than the symbol sizes. Here the domain $\mathcal{D}$ is unbounded but $p_q$ is Gaussian and centered at the origin.

Figure 4

Theoretical prediction for the average energy $ϵ$ for one-dimensional TSP on ring and line domains as a function of $\beta$ (solid line) compared with the Monte Carlo simulations (solid circles). The results of the annealed approximation for the line domain is also shown. Negative $\beta$ corresponds to the maximum TSP. Error bars based on 20 realizations of the quenched points are smaller than the symbol sizes.

Figure 5

Theoretical prediction for the average energy $ϵ$ for the two-dimensional TSP on a sphere, box, and torus as a function of $\beta$. Negative $\beta$ corresponds to the maximum TSP.

Figure 6

Predicted average energy for potential $V\left(x\right)=x^2$ as a function of $\beta$ (solid line) against values measured from Monte Carlo simulations (solid circles).

Figure 7

Predicted average energy for potential $V\left(x\right)=-\ln \left(\mid x\mid \right)$ as a function of $\beta$ (solid line) against values measured from Monte Carlo simulations (solid circles).

Figure 8

Value of $-\ln \left[s\left(x\right)\right]∕\beta$ obtained by numerically solving Eq. (66) at $\beta =30$ (solid line) for the potential $V\left(x\right)=-\mid x\mid$. Also is shown the zero-temperature prediction for this function (dashed line).