Project 1 - Parallel/distributed computing
When measuring the effectiveness of heuristical or statistical approaches (such as neural networks/evolutionary computation) to solving certain apparently difficult problems (such as the travelling salesman problem) we usually make the statement "method A found a reasonably good solution to problem instance P after T timesteps." Sometimes we could even say something stronger, such as "method A found a better solution to problem instance P, and in a shorter time, than method B." However, we still do not have any quantitative information about how close our solution was to the best (optimal) one. We could only do this if we knew in
advance the optimal solution for that problem instance.
Often, the only way to find such "ground-truth" data is through an extremely time-consuming brute force technique. In this project we will attempt to harness the wasted clock-cycles on-campus and further afield to produce a set of benchmark instances for the most awkward (asymmetric and constrained) travelling salesman problem instances over small- to medium-sized graphs. This will involve

• building a centrally-controlled system for parallelising a problem instance and distributing it over the Internet (similar to "SETI at Home"), and
• finding out how solutions to smaller instances of the problem could be incorporated as partial solutions to larger instances of the problem.

• Quantum logic gates with Mathematica*
• Continuous-space processor with Java
• Optical matrix multiplication computer with Java*
• Optical face and fingerprint recognition systems with Matlab*
• Designing your own theoretical processor to tackle an uncomputable problem

URL: http://www.cs.may.ie/~tnaughton
Revised: July 2000
Contact: tomn@cs.may.ie