Neural nets and simulated annealing as tools to combinatorial optimization

Combinatorial optimization is the area within optimization that deals with problems in which an assignment of discrete values to variables is sought at optimizing a certain objective function. Typically, the number of possible assignments is very large, so many of such problems are potentially intractable from the standpoint of their computation complexity. The 1980’s have witnessed the emergence of some unorthodox methods whose goal is to help obtain solutions to those hard problems, which though approximate are often very good. In this article, two such technqiues are reviewed. Artificial neural networks, and the stochastic search technique known as simulated annealing. The first technique realizes the paradigm of ‘collective computation’, which is very attractive for parallel implementations, whereas the second one exploits the idea of ‘uphill climbing’ methods, whose goal is to avoid some of the problems inherent to gradient-descent approaches. The paper presents the main concepts and results related to each of these two techniques, as well as application examples.