Searching for Backbones―a high-performance parallel algorithm for solving combinatorial optimization problems

摘要

A highly efficient parallel algorithm called Searching for Backbones (SfB) is proposed: based on the finding, that many parts of a good configuration for a given optimization problem are the same in all other good solutions, SfB reduces the complexity of this problem by determining these "backbones" and eliminating them in order to get even better solutions in a very short time. Applications and results are presented for the Traveling Salesman Problem and the Vehicle Routing Problem.