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

真实的优化问题，如时间调度问题，其规模通常是合适的，但其复杂的结构使问题的难度。对于这些问题，即使是小规模的实例，也很难开发快速算法。另一方面，对于组合优化问题，如CNF可满足性（SAT）和图问题，也做了大量的工作。特别是1992年提出的一种SAT局部搜索算法，表现出良好的性能。其基本思想是选择一个随机的初始分配和重复移动到更好的邻居.这项工作的目的是解决真实的世界问题的局部搜索算法的SAT.在我们的方法中，我们将原始的实例转换为CNF公式，找到CNF公式的解决方案，然后将解决方案翻译回获得原问题的解决方案.在本研究期间，我们取得了以下成果。(1)虽然把真实的世界 ...更多信息 SAT问题基本上是容易的，但为每道题开发一个翻译算法是一项令人烦恼的工作。我们形式化了一个真实的世界问题，并开发了一个从它到SAT的翻译算法。因此，如果一个人可以用这个公式来表达他/她的问题，他/她可以自动获得一个翻译算法。我们的公式是一般的，足以适用于，例如，上述时间调度问题。(2)到目前为止，人们已经对局部搜索算法做了很多改进，但大多数情况下都是从算法的角度出发。在这项工作中，我们通过实施来改进它。我们的目标是减少局部搜索一步移动所需的时间。为此，我们采用了向量化和PVM，并并行化的局部搜索。我们使用向量超级计算机Fujitsu VPP 800进行向量化，并使用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