Random constraint satisfaction: easy generation of hard (satisfiable) instances

DOI10.1016/j.artint.2007.04.001zbMath1168.68554MaRDI QIDQ1028939

Fred Hemery, Ke Xu, Christophe Lecoutre, Frédéric Boussemart

Publication date: 9 July 2009

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

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

zbMATH Keywords

phase transition; constraint network; hard random instances

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

Related Items

Fractional Edge Cover Number of Model RB, Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, The solution space structure of planted constraint satisfaction problems with growing domains, Incremental Upper Bound for the Maximum Clique Problem, Constructing concrete hard instances of the maximum independent set problem, Bounding the scaling window of random constraint satisfaction problems, Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, A general model and thresholds for random constraint satisfaction problems, STR2: optimized simple tabular reduction for table constraints, A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming, On the phase transitions of random \(k\)-constraint satisfaction problems, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, The scaling window of the model \(d\)-\(k\)-CSP, An upper (lower) bound for Max (Min) CSP, On the parameterized vertex cover problem for graphs with perfect matching, Reasoning from last conflict(s) in constraint programming, On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem, Threshold behaviors of a random constraint satisfaction problem with exact phase transitions, Incomplete inference for graph problems, Weight-based heuristics for constraint satisfaction and combinatorial optimization problems, Pareto optimization for subset selection with dynamic cost constraints, A study on sequential minimal optimization methods for standard quadratic problems, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP, SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem, From MDD to BDD and arc consistency, STR3: a path-optimal filtering algorithm for table constraints, Optimal and efficient filtering algorithms for table constraints, Large hypertree width for sparse random hypergraphs, On the constraint length of random \(k\)-CSP, A taxonomy of exact methods for partial Max-SAT, Complete Boolean satisfiability solving algorithms based on local search, A review on algorithms for maximum clique problems, PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP, NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY, Two Hardness Results on Feedback Vertex Sets, Super Solutions of Random Instances of Satisfiability, A Model to Study Phase Transition and Plateaus in Relational Learning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consistency in networks of relations
• Boosting complete techniques thanks to local search methods
• Exploiting the deep structure of constraint problems
• Many hard examples in exact phase transitions
• An optimal coarse-grained arc consistency algorithm
• An empirical study of phase transitions in binary constraint satisfaction problems
• Locating the phase transition in binary constraint satisfaction problems
• Generalized Arc Consistency for Positive Table Constraints
• Short proofs are narrow—resolution made simple
• Models for Random Constraint Satisfaction Problems
• Theory and Applications of Satisfiability Testing
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems