Searching for backbones and fat: A limit-crossing approach with applications

Sharlee Climer, Weixiong Zhang

Research output: Contribution to conferencePaperpeer-review

25 Scopus citations

Abstract

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 preprocessing 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.

Original languageEnglish
Pages707-712
Number of pages6
StatePublished - 2002
Event18th National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02) - Edmonton, Alta., Canada
Duration: Jul 28 2002Aug 1 2002

Conference

Conference18th National Conference on Artificial Intelligence (AAAI-02), 14th Innovative Applications of Artificial Intelligence Conference (IAAI-02)
Country/TerritoryCanada
CityEdmonton, Alta.
Period07/28/0208/1/02

Fingerprint

Dive into the research topics of 'Searching for backbones and fat: A limit-crossing approach with applications'. Together they form a unique fingerprint.

Cite this