Technical report available

[ahg@eng.cam.ac.uk]

The following technical report is available by anonymous ftp from the
archive of the Speech, Vision and Robotics Group at the Cambridge
University Engineering Department.

                      PROBLEM SOLVING WITH
                      OPTIMIZATION NETWORKS

                           PhD Thesis

                           Andrew Gee

              Technical Report CUED/F-INFENG/TR 150

	    Cambridge University Engineering Department 
		        Trumpington Street 
		        Cambridge CB2 1PZ 
			     England 


                             Summary

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.

************************ How to obtain a copy ************************

Via FTP:

unix> ftp svr-ftp.eng.cam.ac.uk
Name: anonymous
Password: (type your email address)
ftp> cd reports
ftp> binary
ftp> get gee_tr150.ps.Z
ftp> quit
unix> uncompress gee_tr150.ps.Z
unix> lpr gee_tr150.ps (or however you print PostScript)

NB. This is a large file, expanding to 3.8 MBytes of uncompressed
    Postscript, and printing on 144 pages.