Experiments of Intelligent Algorithms on Ramsey Graphs

Jihad Mohamad AlJaam

Department of Computer Science and Engineering, Qatar University, Qatar

Abstract: Ramsey numbers are known to be hard combinatorial problems that have many important applications including number theory, algebra, geometry, topology, set theory, logic, ergodic theory, information theory, and theoretical computer science.  The evaluation of Ramsey numbers using intelligent algorithms has been extensively studied in the last decades and only few numbers are currently known. Almost all of these methods failed to find the exact value of Ramsey numbers as they are over constraints problem. They have succeeded only to improve some upper and lower bounds of these numbers. In this work, we have tested the following intelligent algorithm: Backtracking, local search, tabu search and simulated annealing on some extremely hard instances of Ramsey numbers namely R (5, 9) - 120 and R (6, 8) - 121. As we failed to solve these hard instances using the previous techniques, we decided to combine them together in a hybrid metaheuristic algorithm and succeeded to generate the expected solutions. This new hybrid algorithm seems efficient and promising. It can be applied also on different combinatorial problems even if deep mathematical properties of the problems' domain are not on hand.

Keywords: Metaheuristic, hybrid algorithms, optimization, combinatorics, Ramsey numbers.