Random constraint satisfaction: easy generation of hard (satisfiable) instances
From MaRDI portal
Publication:1028939
DOI10.1016/j.artint.2007.04.001zbMath1168.68554OpenAlexW1990734013MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (43)
Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ A review on algorithms for maximum clique problems ⋮ Super Solutions of Random Instances of Satisfiability ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ 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 ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT 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 ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ Maximum independent sets and supervised learning ⋮ Threshold behaviors of a random constraint satisfaction problem with exact phase transitions ⋮ STR2: optimized simple tabular reduction for table constraints ⋮ Incomplete inference for graph problems ⋮ A taxonomy of exact methods for partial Max-SAT ⋮ Complete Boolean satisfiability solving algorithms based on local search ⋮ Weight-based heuristics for constraint satisfaction and combinatorial optimization problems ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ A Model to Study Phase Transition and Plateaus in Relational Learning ⋮ Fractional Edge Cover Number of Model RB ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ Pareto optimization for subset selection with dynamic cost constraints ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Reasoning from last conflict(s) in constraint programming ⋮ From MDD to BDD and arc consistency ⋮ A study on sequential minimal optimization methods for standard quadratic problems ⋮ STR3: a path-optimal filtering algorithm for table constraints ⋮ Optimal and efficient filtering algorithms for table constraints ⋮ Large hypertree width for sparse random hypergraphs ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length ⋮ On the constraint length of random \(k\)-CSP
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
This page was built for publication: Random constraint satisfaction: easy generation of hard (satisfiable) instances
