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

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.