Paper in neuroprose

[A. H. Gee]

************** PLEASE DO NOT FORWARD TO OTHER NEWSGROUPS ****************

The following technical report has been placed in the neuroprose 
archives at Ohio State University:

                    POLYHEDRAL COMBINATORICS
                       AND NEURAL NETWORKS

                  Andrew Gee and Richard Prager

	       Technical Report CUED/F-INFENG/TR 100

	    Cambridge University Engineering Department 
		        Trumpington Street 
		        Cambridge CB2 1PZ 
			     England 


                             Abstract

The often disappointing performance of optimizing neural networks can
be partly attributed to the rather ad hoc manner in which problems are
mapped onto them for solution. In this paper a rigorous mapping is
described for quadratic 0-1 programming problems with linear equality
and inequality constraints, this being the most general class of
problem such networks can solve. The problem's constraints define a
polyhedron P containing all the valid solution points, and the mapping
guarantees strict confinement of the network's state vector to P.
However, forcing convergence to a 0-1 point within P is shown to be
generally intractable, rendering the Hopfield and similar models
inapplicable to the vast majority of problems. Some alternative
dynamics, based on the principle of tabu search, are presented as a
more coherent approach to general problem solving. When tested on a
large database of solved problems, the alternative dynamics produced
some very encouraging results. 

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

a) Via FTP:

unix> ftp archive.cis.ohio-state.edu (or 128.146.8.52)
Name: anonymous
Password: (type your email address)
ftp> cd pub/neuroprose
ftp> binary
ftp> get gee.poly.ps.Z
ftp> quit
unix> uncompress gee.poly.ps.Z
unix> lpr gee.poly.ps (or however you print PostScript)

Please note that a couple of the figures in the paper were produced
on an Apple Mac, and the resulting PostScript is not quite standard.
People using an Apple LaserWriter should have no problems though.

b) Via postal mail:

Request a hardcopy from

Andrew Gee,
Speech Laboratory,
Cambridge University Engineering Department, 
Trumpington Street, 
Cambridge CB2 1PZ,
England.

or email me: ahg at eng.cam.ac.uk