Prototyping a general solver framework of combinatorial optimization problems on a volunteer computing environment

点击翻译按钮获取中文摘要

We had the following two research goals at the beginning of this project: 1) Evaluating the effectiveness of a large-scale parallelization for combinatorial optimization problems on a volunteer computing environment, 2) Evaluating a JDK5.0-based general solver framework for combinatorial optimization problems. Together with these goals, we had a plan to develop a visualization tool for activity of solvers.When we proposed this research, JXTA technology had attracted considerable attention. However, this technology seemed be not so powerful for our research goal. After we investigated computational environments for our research, we met a software tool Overlay Waver and made a prototype system on an overlay network using Overlay Weaver. Since Overlay Waver has an emulator of distributed environments, we could conduct large-scale computational simulations.On one hand, we did not develop a JDK5.0-based general solver framework. We should reconsider whether a Java-based system is appropriate or not for our goals. On the other hand, we developed an excellent visualization tool which displays runtime behavior of a solving algorithm for hard problem instances.Nowadays, the term "Volunteer computing" becomes a technical term in information technology. We should restart a similar project like this project in the near future, when volunteer computing environment becomes more mature one.