|
|
 |
 |
|
| Distributed Combinatorial Problem Solving |
Combinatorial search problems often require vast amounts computation time. Examples include production scheduling and timetabling problems for which no efficient algorithms are known. Systematic search, even supported by sophisticated constraint programming technology, often requires a huge computational effort. The goal of the Magic Knights project is to provide an infrastructure in which the computation power of hundreds or even thousands of idle PCs can be harnessed for solving such problems. The infrastructure allows to solve hard combinatorial search problems by distributing computing time over a network of registered PCs. The registration and activation of the PC for contributing computing time is achieved through a PC screen saver. As a demonstration application, we implemented a distributed solver for a famous combinatorial search problem using the Magic Knights infrastructure. |
|