PROBLEM SOLVING WITH OPTIMIZATION NETWORKS (PHD THESIS)
Andrew H. Gee
July 1993
Combinatorial optimization problems, which are characterized by a discrete set as opposed to a continuum of possible solutions, occur in many areas of engineering, science and management. Such problems have so far resisted efficient, exact solution, despite the attention of many capable researchers over the last few decades. It is not surprising, therefore, that most practical solution algorithms abandon the goal of finding the optimal solution, and instead attempt to find an approximate, useful solution in a reasonable amount of time. A recent approach makes use of highly interconnected networks of simple processing elements, which can be programmed to compute approximate solutions to a variety of difficult problems. When properly implemented in suitable parallel hardware, these `optimization networks' are capable of extremely rapid solutions rates, thereby lending themselves to real-time applications.
This thesis takes a detailed look at problem solving with optimization networks. Three important questions are identified concerning the applicability of optimization networks to general problems, the convergence properties of the networks, and the likely quality of the networks' solutions. These questions are subsequently answered using a combination of rigorous analysis and simple, illustrative examples. The investigation leads to a clearer understanding of the networks' capabilities and shortcomings, confirmed by extensive experiments. It is concluded that optimization networks are not as attractive as they might have previously seemed, since they can be successfully applied to only a limited number of problems exhibiting special, amenable properties.
Key words: Combinatorial optimization, neural networks, mean field annealing.
NB: This is a large file, expanding to 3.8 MBytes of uncompressed PostScript, and printing on 144 pages.
If you have difficulty viewing files that end '.gz',
which are gzip compressed, then you may be able to find
tools to uncompress them at the gzip
web site.
If you have difficulty viewing files that are in PostScript, (ending
'.ps' or '.ps.gz'), then you may be able to
find tools to view them at
the gsview
web site.
We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.