Optimization Online


Solving maximum cut problems by simulated annealing

Tor G.J. Myklebust(tmyklebu***at***gmail.com)

Abstract: This paper gives a straightforward implementation of simulated annealing for solving maximum cut problems and compares its performance to that of some existing heuristic solvers. The formulation used is classical, dating to a 1989 paper of Johnson, Aragon, McGeoch, and Schevon. This implementation uses no structure peculiar to the maximum cut problem, but its low per-iteration cost allows it to find better solutions than were previously known for 40 of the 89 standard maximum cut instances tested within a few minutes of computation.

Keywords: maximum cut, simulated annealing

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: arXiv:1505.03068

Download: [Postscript][PDF]

Entry Submitted: 05/19/2015
Entry Accepted: 05/20/2015
Entry Last Modified: 05/19/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society