It does take a long time to search completely for max-cliques but it may not be necessary to search through all the possibilities. We can take a collection of possibilities, rate them according to how close they are to an estimate of the max-clique, mix the best possibilities together, and repeat until we have the best solution. One group of algorithms that do this kind of computing are Genetic Algorithms (GA). Goldberg explains GAs this way:
Genetic algorithms are search algorithms based on the mechanics of natural selection and natural genetics. They combine survival of the fittest among string structures with a structured yet randomized information exchange to form a search algorithm with some of the innovative flair of human search. In every generation, a new set of artificial creatures (strings) is created using bits and pieces of the fittest of the old; an occasional new part is tried for good measure. While randomized, genetic algorithms are no simple random walk. They efficiently exploit historical information to speculate on new search points with expected improved performance. [Gol89]
Soule and Foster created a GA to search for max-cliques in general graphs [SF95]. Since this GA was designed to perform well on general graphs and the Keller graphs are very unique, they cause the GA some problems, lowing performance. The GA needs non-uniformity to be able to select the best solutions to mate. The Keller graphs are very uniform: all the nodes have an equal number of arcs, and there are a large number cliques in these graphs [LS92]. Given this difficulty, preliminary results are still promising and tailoring the GA to the Keller graphs might make a solution to the Keller conjecture possible.