Considering a complex problem in Computational Physics and Operations Research, respectively, one mostly faces the problem that no exact algorithms exist to solve this problem. If the instance of the problem is of a large size, heuristic methods have to be used in order to achieve relatively good results or even the global optimum, e.g., physical optimization algorithms like Simulated Annealing and Threshold Accepting have proved to provide solutions of a high quality.
Comparing different good configurations for a given optimization problem, many parts being equal in all of them can be found. Obviously, these ``backbones'' are already optimally solved. Each further optimization run, which again leads to these backbones, can then be considered as wasting computation time.
Searching for Backbones is a parallel algorithm that makes use of the existence of backbones: first of all, a certain number of independent optimization runs is performed on the considered problem. All slave processors send their results to the master, which compares them and determines the backbones. These backbones are assumed to be optimal and even to be part of the global optimum. The information about these backbones is returned to the slave processors. They perform a new optimization run, in which the already determined backbones are not to be destroyed. The new solutions are supposed to be of higher quality than the former ones, as the optimization process should have been easier for the slave processors in this second iteration: they could concentrate on parts that are obviously more difficult to solve because the backbones (the easy parts) are held constant. Therefore, the former solutions are neglected. The new solutions are again compared for equal parts. Usually, they coincide in more parts than the previous ones, such that longer and more backbones are received. This procedure of performing independent optimization runs considering the backbones and comparing the results for a new extended set of backbones is repeated several times until all processors produce the same (quasi) optimum solution at the end.
Searching for Backbones can thus be considered as an algorithm, which gradually reduces the complexity of a problem. The definition and determination of backbones is strongly problem dependent, however, mostly the definition of an item which shall be identified as a backbone is relatively straightforward. I will present the approach and results for sequencing problems, such as the Traveling Salesman Problem and the Vehicle Routing Problem, in which a backbone consists of a sequence of nodes, which is equally found in all solutions.
Keywords: Massive Parallelization, Traveling Salesman Problem, Vehicle Routing Problem, Simulated Annealing, Threshold Accepting