Searching for Backbones and Fat: A Limit-Crossing Approach with Applications

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Search

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 asset when attempting to solve complex problems. In this paper, 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 information 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 various instances of the Asymmetric Traveling Salesman Problem (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 dramatic performance improvements.