Abstract for gee_tr100

Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR100

POLYHEDRAL COMBINATORICS AND NEURAL NETWORKS

Andrew H. Gee and Richard W. Prager

May 1992

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.


(ftp:) gee_tr100.ps.Z (http:) gee_tr100.ps.Z
PDF (automatically generated from original PostScript document - may be badly aliased on screen):
  (ftp:) gee_tr100.pdf | (http:) gee_tr100.pdf

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.