A fast search of approximate feasible solutions for real-world combinatorial problems

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

Instances of real world optimization problems, such as time scheduling problem, are usually of appropriate size, but its complicated structure makes the problem harder. It is difficult to develop fast algorithms for those problems even for small size instances. On the other hand, much work have been done for combinatorial optimization problems such as CNF Satisfiability (SAT) and graph problems. Especially, it has been constantly reported that a local search algorithm for SAT, developed in 1992, shows good performance. Its basic idea is to select a random initial assignment and repeats moving to better neighbors.The purpose of this work is to solve real world problems using the local search algorithm for SAT.In our approach, we translate the original instance to a CNF formula, find a solution of the CNF formula, and then translate the solution back to obtain the solution of the original problem. In this research period, we obtained following results.(1) Although translating real world … More problems to SAT is basically easy, it is a bothering work to develop a translation algorithm for each problem. We formalized a real world problem and developed a translation algorithm from it to SAT.Thus, if one can formulate his/her problem in this formulation, he/she can obtain a translation algorithm automatically. Our formulation is general enough to apply for, for example, the time scheduling problem above.(2) Up to now, a lot of improvements have been done for the local search algorithm, which are in most cases from algorithmic viewpoints. In this work, we improved it by implementation. Our purpose is to reduce the time needed for one step movement of local search. For this purpose, we adopted vectorization and PVM, and parallelized the local search. We used vector supercomputer Fujitsu VPP800 for vectorization, and a cluster of 70 workstations for PVM.We conducted experiments using benchmark instances and verified the speedup. Furthermore, we tried our approach for time scheduling problem. We were able to solve an instance within two hours which were not solved even for two days before our improvement. We presented results at Workshop of Algorithm Engineering, and were in vited to ACM Journal of Experimental Algorithmics. Less