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

现实世界中的优化问题的实例，如时间调度问题，通常具有适当的大小，但其复杂的结构使问题变得更加困难。即使对于小规模的实例，也很难为这些问题开发快速算法。另一方面，对于组合优化问题，如CNF可满足性(SAT)和图问题，已经做了大量的工作。特别是，不断有报道称，1992年开发的SAT局部搜索算法表现出了良好的性能。该算法的基本思想是选择一个随机的初始分配，然后重复移动到更好的邻域，目的是利用SAT的局部搜索算法来解决现实世界中的问题，将原始实例转化为CNF公式，求出CNF公式的解，然后再将解转换回来，得到原始问题的解。在本研究期间，我们取得了以下成果：(1)虽然翻译现实世界中的…更多的问题到SAT基本上是很容易的，为每个问题开发一个翻译算法是一项烦人的工作。我们形式化了一个现实世界的问题，并开发了一个从它到SAT的翻译算法，因此，如果一个人可以用这个公式来描述他/她的问题，他/她就可以自动获得一个翻译算法。到目前为止，对局部搜索算法已经做了大量的改进，大多数情况下都是从算法的角度出发的。在这项工作中，我们通过实施对其进行了改进。我们的目的是减少局部搜索的一步移动所需的时间。为此，我们采用了矢量化和PVM，并对局部搜索进行了并行化。我们使用向量超级计算机Fujitsu VPP800进行矢量化，并使用由70台工作站组成的集群来进行PVM。我们使用基准实例进行了实验，并验证了加速比。此外，我们还尝试了我们的方法来解决时间调度问题。我们能够在两个小时内解决一个实例，而在我们改进之前，甚至有两天都没有解决。我们在算法工程研讨会上展示了结果，并被选为ACM实验算法杂志。较少

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