Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems - initial results

Weixiong Zhang, Joseph C. Pemberton

Research output: Contribution to conferencePaperpeer-review

5 Scopus citations

Abstract

It has been shown that there exists a transition in the average-case complexity of searching a random tree, from exponential to polynomial in the search depth. We develop a state-space transformation method, called ε-transformation, that makes use of this complexity transition to find a suboptimal solution. The expected number of random tree nodes expanded by branch-and-bound (BnB) using ε-transformation is cubic in the search depth, and the relative error of the solution cost compared to the optimalsolution cost is bounded by a small constant. We also present an iterative version of ε-transformation that can be used to find both optimal and suboptimal solutions. Depth-first BnB (DFBnB) using iterative ε-transformation significantly improves upon truncated DFBnB on random trees with large branching factors and deep goal nodes, finding better solutions sooner on average. On the asymmetric traveling salesman problem, DFBnB using ε-transformation outperforms a well-known local search method, and DFBnB using iterative ε-transformation is superior to truncated DFBnB.

Original languageEnglish
Pages895-900
Number of pages6
StatePublished - 1994
EventProceedings of the 12th National Conference on Artificial Intelligence. Part 1 (of 2) - Seattle, WA, USA
Duration: Jul 31 1994Aug 4 1994

Conference

ConferenceProceedings of the 12th National Conference on Artificial Intelligence. Part 1 (of 2)
CitySeattle, WA, USA
Period07/31/9408/4/94

Fingerprint

Dive into the research topics of 'Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems - initial results'. Together they form a unique fingerprint.

Cite this