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

DOI10.1016/j.artint.2004.04.001zbMath1085.68678OpenAlexW1586919270MaRDI 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 satisfiabilityLocal searchBackbone guided searchConfiguration landscapeMaximum Boolean satisfiability

Mathematics Subject Classification ID

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

Related Items (10)

The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability ⋮ An effective hybrid search algorithm for the multiple traveling repairman problem with profits ⋮ Boosting quantum annealer performance via sample persistence ⋮ Analysis of local search landscapes for \(k\)-SAT instances ⋮ Combining VNS with constraint programming for solving anytime optimization problems ⋮ Decomposing SAT Instances with Pseudo Backbones ⋮ Backbone analysis and algorithm design for the quadratic assignment problem ⋮ Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem ⋮ Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP ⋮ Graph coloring by multiagent fusion search

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

This page was built for publication: Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability