Exploiting the deep structure of constraint problems

DOI10.1016/0004-3702(94)90104-XzbMath0938.68827OpenAlexW2169185944MaRDI QIDQ1342216

Colin P. Williams, Tad Hogg

Publication date: 9 February 1995

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

Full work available at URL: https://doi.org/10.1016/0004-3702(94)90104-x

Mathematics Subject Classification ID

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

Related Items (29)

The hardest constraint problems: A double phase transition ⋮ Revisiting global constraint satisfaction ⋮ Phase transitions and the search problem ⋮ The satisfiability constraint gap ⋮ An empirical study of phase transitions in binary constraint satisfaction problems ⋮ Refining the phase transition in combinatorial search ⋮ Locating the phase transition in binary constraint satisfaction problems ⋮ Implicates and prime implicates in random 3-SAT ⋮ A study of complexity transitions on the asymmetric traveling salesman problem ⋮ Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems ⋮ Problem structure heuristics and scaling behavior for genetic algorithms ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Experimental complexity analysis of continuous constraint satisfaction problems. ⋮ Another look at the phenomenon of phase transition ⋮ Constructive generation of very hard 3-colorability instances ⋮ Fine-grained conflict resolution in constraint satisfaction problems ⋮ Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ Quantum computation and quantum information† ⋮ SAT vs. Translation Based decision procedures for modal logics: a comparative evaluation ⋮ The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$ ⋮ EPIDEMIOLOGY MODEL ON SHORTCUT AND SMALL WORLD NETWORKS ⋮ Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ A new method for testing decision procedures in modal logics ⋮ A framework for structured quantum search. ⋮ GA performance distributions and randomly generated binary constraint satisfaction problems. ⋮ Building decision procedures for modal logics from propositional decision procedures: The case study of modal \(K(m)\).

Cites Work

• Optimization by Simulated Annealing
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exploiting the deep structure of constraint problems