Searching for backbones and fat: a limit-crossing approach with applications
Sharlee Climer, Weixiong Zhang · 2002
Backbone variables are the elements that are common to all optimal solutions of a problem instance. We call variables that are absent from every optimal solution fat variables. Identification of backbone and fat variables is a valuable as-set when attempting to solve complex problems. In this pa-per, we demonstrate a method for identifying backbones and fat. Our method is based on an intuitive concept, which we refer to as limit crossing. Limit crossing occurs when we force the lower bound of a graph problem to exceed the upper bound by applying the lower-bound function to a constrained version of the graph. A desirable feature of this procedure is that it uses approximation functions to derive exact infor-mation about optimal solutions. In this paper, we prove the validity of the limit-crossing concept as well as other related properties. Then we exploit limit crossing and devise a pre-processing tool for discovering backbone and fat arcs for var-ious instances of the Asymmetric Traveling Salesman Prob-lem (ATSP). Our experimental results demonstrate the power of the limit-crossing method. We compare our pre-processor with the Carpaneto, Dell’Amico, and Toth pre-processor for several different classes of ATSP instances and reveal dra-matic performance improvements.