Epsilon-Transformat ion: Exploiting Phase Transitions to Solve Combinatorial Optimization Problems - Initial Results*
Weixiong Zhang, Charles Joseph · 1994
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 e-transformation, that makes use of this com-plexity transition to find a suboptimal solution. The expected number of random tree nodes expanded by branch-and-bound (BnB) using e-transformation is cubic in the search depth, and the relative error of the solution cost compared to the optimal solution cost is bounded by a small constant. We also present an iter-ative version of e-transformation that can be used to find both optimal and suboptimal solutions. Depth-first BnB (DFBnB) using iterative e-transformation significantly improves upon truncated DFBnB on ran-dom trees with large branching factors and deep goal nodes, finding better solutions sooner on average. On the asymmetric traveling salesman problem, DFBnB using e-transformation outperforms a well-known lo-cal search method, and DFBnB using iterative e-transformation is superior to truncated DFBnB.