Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability

DOI10.1016/j.artint.2004.04.001zbMath1085.68678MaRDI QIDQ814612

Weixiong Zhang

Publication date: 7 February 2006

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

Full work available at URL: https://doi.org/10.1016/j.artint.2004.04.001

zbMATH Keywords

Boolean satisfiability; Local search; Backbone guided search; Configuration landscape; Maximum Boolean satisfiability

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP, Analysis of local search landscapes for \(k\)-SAT instances, Combining VNS with constraint programming for solving anytime optimization problems, Backbone analysis and algorithm design for the quadratic assignment problem, Graph coloring by multiagent fusion search, Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem

Uses Software

• SATLIB
• Walksat
• BG-WalkSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new adaptive multi-start technique for combinatorial global optimizations
• Phase transitions and the search problem
• Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
• Determining computational complexity from characteristic ‘phase transitions’
• A machine program for theorem-proving
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem