Computing exact ground states of hard Ising spin glass problems by branch-and-cut.

*(English)*Zbl 1059.90147
Hartmann, Alexander K. (ed.) et al., New optimization algorithms in physics. Weinheim: Wiley-VCH (ISBN 3-527-40406-6/hbk). 47-69 (2004).

From the introduction: In this chapter we explain the branch-and-cut technique for exact ground-state computation and show its potential for the study of ground-state properties of lsing spin glasses.

We show that the ground-state problem for lsing spin glasses is equivalent to the max-cut problem that is well known in combinatorial optimization and has a number of further applications. From then on, we concentrate on properties of and algorithmic approaches to max-cut. We start by introducing a general scheme for solving hard max-cut problems which consists of specializing the well known branch-and-bound method to max-cut. In branch-and-bound, relaxations play a crucial role, and as a prerequisite for the branch-and-cut algorithm we are aiming at, we study linear programming relaxations of max-cut in some detail. After these preparations, we outline the main components of our branch-and-cut method. We present some recent results obtained with exact ground-state computations in the context of studying the nature of the spin-glass phase. Then we comment on advantages of branch-and-cut for exact groundstate computations. We close with some challenges which we see for the future.

For the entire collection see [Zbl 1054.90002].

We show that the ground-state problem for lsing spin glasses is equivalent to the max-cut problem that is well known in combinatorial optimization and has a number of further applications. From then on, we concentrate on properties of and algorithmic approaches to max-cut. We start by introducing a general scheme for solving hard max-cut problems which consists of specializing the well known branch-and-bound method to max-cut. In branch-and-bound, relaxations play a crucial role, and as a prerequisite for the branch-and-cut algorithm we are aiming at, we study linear programming relaxations of max-cut in some detail. After these preparations, we outline the main components of our branch-and-cut method. We present some recent results obtained with exact ground-state computations in the context of studying the nature of the spin-glass phase. Then we comment on advantages of branch-and-cut for exact groundstate computations. We close with some challenges which we see for the future.

For the entire collection see [Zbl 1054.90002].