Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems

DOI10.1016/0004-3702(95)00057-7OpenAlexW2091208389MaRDI QIDQ2674191

Weixiong Zhang, Joseph C. Pemberton

Publication date: 22 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00057-7

zbMATH Keywords

complexityphase transitionsbranch and boundtransformationtraveling salesman problemproblem solvingsearchBoolean satisfiabilitycombinatorial optimiziation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

A study of complexity transitions on the asymmetric traveling salesman problem ⋮ Iterative state-space reduction for flexible computation ⋮ Performance of linear-space search algorithms ⋮ Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Exploiting the deep structure of constraint problems
• Searching for an optimal path in a tree with random costs
• A study of complexity transitions on the asymmetric traveling salesman problem
• Using branch-and-bound algorithms to obtain suboptimal solutions
• Generalized best-first search strategies and the optimality of A*
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Local Search for the Asymmetric Traveling Salesman Problem
• Flowshop scheduling with limited temporary storage
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Computational Efficiency of Approximate Branch-and-Bound Algorithms
• Branch-and-Bound Methods: A Survey
• Letter to the Editor—An Experimental Investigation and Comparative Evaluation of Flow-Shop Scheduling Techniques
• The Traveling-Salesman Problem and Minimum Spanning Trees
• On the Flow-Shop Sequencing Problem with No Wait in Process^†
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Performance of linear-space search algorithms