Disordered systems and combinatorial optimization problems

[Next]:

Microscopic modeling of financial assets

[Up]:

Projects

[Previous]:

Stochastic dynamics

[Contents]

[Index]

Disordered systems and combinatorial optimization problems

Collaborator: A. Bovier

Cooperation with: I. Kurkova (Université Paris VI, France)

Supported by: ESF Programme RDSES, DFG Research Center MATHEON, project E1

Description:

It has long been noted that many problems of combinatorial optimization are structurally similar to disordered systems in statistical mechanics. The maybe simplest of these problems is the number partitioning problem. The connection of this problem to statistical mechanics, and in particular to the random energy model, has been pointed out by St. Mertens [1], 2]. The number partitioning problem is a classical optimization problem: Given N numbers n₁, n₂,..., n_N, find a way of distributing them into two groups, such that their sums in each group are as similar as possible. What is needed in practice is an algorithm that, when presented with the N numbers, finds the optimal partitioning as quickly as possible. Since the number of possible partitions is 2^N, simply trying them all out is not going to be a very clever way of doing this. Rather surprisingly, however, it is quite hard to do very much better, as this problem is (believed) to be N - P-hard, i.e. no algorithm can be found that is sure to solve the problem in a time that is polynomial in the size N!

As pointed out by Mertens, this fact can to some extent be understood by realizing that the problem is rather closely related to mean-field spin glasses, and in particular the random energy model. Of course, the occurrence of the number 2^N should already have made us suspect that. Indeed, any partition of the set {1,..., N} into two disjoint subsets, $\Lambda_{1}^{}$ , $\Lambda_{2}^{}$ , is equivalent to a spin configuration $\sigma$ $\in$ $\mathcal {S}$ _N via $\Lambda_{1}^{}$ $\equiv$ {i : $\sigma_{i}^{}$ = + 1} and $\Lambda_{2}^{}$ = $\equiv$ {i : $\sigma_{i}^{}$ = - 1}. Moreover, the quantity to be minimized is

$\displaystyle \left\vert\vphantom{ \sum_{i\in \Lambda_1}n_i-\sum_{i\in \Lambda_2}n_i}\right.$ $\displaystyle \sum_{{i\in \Lambda_1}}^{}$ n_i - $\displaystyle \sum_{{i\in \Lambda_2}}^{}$ n_i $\displaystyle \left.\vphantom{ \sum_{i\in \Lambda_1}n_i-\sum_{i\in \Lambda_2}n_i}\right\vert$ = $\displaystyle \left\vert\vphantom{\sum_{i=1}^N n_i\sigma _i}\right.$ $\displaystyle \sum_{{i=1}}^{N}$ n_i $\displaystyle \sigma_{i}^{}$ $\displaystyle \left.\vphantom{\sum_{i=1}^N n_i\sigma _i}\right\vert$ $\displaystyle \equiv$ H_N( $\displaystyle \sigma$ ).

This is a spin-system Hamiltonian depending on the parameters n_i. While statistical mechanics will not provide algorithms that solve this problem, they will say something about the solutions, i.e. the minimum, and more generally, the energy landscape. This should then be useful to people who want to find algorithms.

The properties of the optimal solutions conjectured by Mertens can be described as follows:

(i): Optimal partitions have a discrepancy of the order C(N) = 2^-N+1 $\sqrt{{\frac {2\pi N} {12}}}$ .
(ii): The discrepancies of the best, second best, etc. partitions, when divided by C(N), converge to the standard Poisson process on $\Bbb$ R₊.
(iii): The k best partitions are independently and uniformly distributed in the space of partitions, and, in particular, have maximal distance from each other.

Borgs et al [4], [3] proved that this conjecture is true.

In [5], we proved an analogous result in the generalized case when N numbers are to be partitioned into k $\geq$ 2 groups (of equal cardinality) in such a way that the sums in each group are to be as similar as possible. We considered the successive differences of the sums in each group, and showed that the properly rescaled vector of these differences converges to a Poisson point process on $\Bbb$ R^k-1. This problem turned out to be much harder than expected, due to the possibility of linear relations. A key element in the proof is a very general theorem that established criteria for the convergence of extremal processes to Poisson processes that is of independent interest and that we expect to be useful in many related problems.

References:

S. MERTENS, A physicist's approach to number partitioning. Phase transitions in combinatorial problems (Trieste, 1999), Theoret. Comput. Sci., 265 (2001), pp. 79-108.
H. BAUKE, S. FRANZ, S. MERTENS, Number partitioning as random energy model, J. Stat. Mech.: Theor. Exp., (2004), P04003.
C. BORGS, J.T. CHAYES, S. MERTENS, B. PITTEL Phase diagram for the constrained integer partitioning problem, Random Structures Algorithms, 24 (2004), pp. 315-380.
CH. BORGS, J.T. CHAYES, B. PITTEL, Phase transition and finite-size scaling for the integer partitioning problem, Random Structures Algorithms, 19 (2001), pp. 247-288.
A. BOVIER, I. KURKOVA, Poisson convergence in the restricted k-partitioning problem, WIAS Preprint no. 964, 2002, submitted.