On the Landscape of Combinatorial Optimization Problems

Mohammadhassan Tayaraninajaran, Adam Prugel-Bennett

Research output: Contribution to journalArticlepeer-review

40 Citations (Scopus)


This paper carries out a comparison of the fitness landscape for four classic optimization problems: Max-Sat, graph-coloring, traveling salesman, and quadratic assignment. We have focused on two types of properties, local average properties of the landscape, and properties of the local optima. For the local optima we give a fairly comprehensive description of the properties, including the expected time to reach a local optimum, the number of local optima at different cost levels, the distance between optima, and the expected probability of reaching the optima. Principle component analysis is used to understand the correlations between the local optima. Most of the properties that we examine have not been studied previously, particularly those concerned with properties of the local optima. We compare and contrast the behavior of the four different problems. Although the problems are very different at the low level, many of the long-range properties exhibit a remarkable degree of similarity.
Original languageEnglish
Pages (from-to)420-434
JournalIEEE Transactions on Evolutionary Computation
Issue number3
Publication statusPublished - 11 Sept 2013


Dive into the research topics of 'On the Landscape of Combinatorial Optimization Problems'. Together they form a unique fingerprint.

Cite this