Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!pyramid!nsc!andrew
From: andrew@nsc.nsc.com (andrew)
Newsgroups: comp.ai.neural-nets
Subject: Re: implementation of "traveling salesman algorithm" on CM
Summary: Optimisations akin to TSP
Keywords: TSP, Nonlinear Optimization, Optimal Dynamic Control, Economics Hopfield's work
Message-ID: <9775@nsc.nsc.com>
Date: 11 Feb 89 03:12:05 GMT
References: <1637@cps3xx.UUCP> <1233@usfvax2.EDU> <476@madnix.UUCP>
Organization: National Semiconductor, Santa Clara
Lines: 32

A recently addressed "solution" by supercomputer to a long-standing maths
conjecture - that of the finite projective plane - now exists for planes up
to order 10 (Science News, Dec 24 & 31, 1988), whereby 1000's of hours
of Cray time was needed! This looks like a nice place for a net and a Cray
to do battle... the constraints are simply expressed:
- for order k, construct a square matrix with k**2 + k + 1 rows/columns
- fill the matrix with 0's and 1's, such that:
	- every row contains exactly k + 1  1's
	- every possible pair of rows has exactly one column in which
	  both have a '1'

I have successfully solved this for low orders using the linear "schema"
cs (constraint satisfaction) program from "Explorations...PDP".
Boltzmann is lousy, but I haven't tried Harmony yet.

The net scales as order O(k**4) in # nodes and O(k**4 - k**6) (to be
resolved) in # weights. For order 10, one needs about 12K neurons and
about 2M weights. Out there exists hardware (which I don't have) to
get over 1M cps, so it's obviously in range of current virtual net
simulators.

Interested parties contact me at:

	Andrew Palfreyman, MS D3969		PHONE:  408-721-4788 work
	National Semiconductor				408-247-0145 home
	2900 Semiconductor Dr.			there's many a slip
	P.O. Box 58090				'twixt cup and lip
	Santa Clara, CA  95052-8090

	DOMAIN: andrew@logic.sc.nsc.com  
	ARPA:   nsc!logic!andrew@sun.com
	USENET: ...{amdahl,decwrl,hplabs,pyramid,sun}!nsc!logic!andrew