Article

Generating Satisfiable Problem Instances

Authors:

Dimitris Achlioptas,

Carla P. Gomes,

Henry A. Kautz,

Bart SelmanAuthors Info & Claims

Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence

Pages 256 - 261

Published: 30 July 2000 Publication History

Abstract

No abstract available.

Cited By

View all

Moreno-Scott JOrtiz-Bayliss JTerashima-Marín HConant-Pablos S(2016)Experimental matching of instances to heuristics for constraint satisfaction problemsComputational Intelligence and Neuroscience10.1155/2016/73490702016(37-37)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2016/7349070
Giráldez-Cru JLevy J(2016)Generating SAT instances with community structureArtificial Intelligence10.1016/j.artint.2016.06.001238:C(119-134)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.artint.2016.06.001
Nguyen VMai SThang HPhuong LDe Raedt LDeville YBui MLinh TOanh NSang DNgoc N(2015)A New Method to Encode the At-Most-One Constraint into SATProceedings of the 6th International Symposium on Information and Communication Technology10.1145/2833258.2833293(46-53)Online publication date: 3-Dec-2015
https://dl.acm.org/doi/10.1145/2833258.2833293
Show More Cited By

Recommendations

Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden
The generation of SAT instances is an important issue in computer science, and it is useful for researchers to verify the effectiveness of SAT solvers. Addressing this issue could inspire researchers to propose new search strategies. SAT problems exist in ...
Generating Instances for MAX2SAT with Optimal Solutions

A test instance generator (an instance generator for short) for MAX2SAT is a procedure that produces, given a number n of variables, a 2-CNF formula F of n variables (randomly chosen from some reasonably large domain), and simultaneously provides one of ...
Hidden gold in random generation of SAT satisfiable instances
IJCAI'97: Proceedings of the 15th international joint conference on Artifical intelligence - Volume 1

Evaluation of incomplete algorithms that solve SAT requires to generate hard satisfiable instances. For that purpose, the kSAT uniform random generation is not usable. The other generators of satisfiable instances generate instances that are not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence

July 2000

1108 pages

ISBN:0262511126

Publisher

AAAI Press

Publication History

Published: 30 July 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moreno-Scott JOrtiz-Bayliss JTerashima-Marín HConant-Pablos S(2016)Experimental matching of instances to heuristics for constraint satisfaction problemsComputational Intelligence and Neuroscience10.1155/2016/73490702016(37-37)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2016/7349070
Giráldez-Cru JLevy J(2016)Generating SAT instances with community structureArtificial Intelligence10.1016/j.artint.2016.06.001238:C(119-134)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.artint.2016.06.001
Nguyen VMai SThang HPhuong LDe Raedt LDeville YBui MLinh TOanh NSang DNgoc N(2015)A New Method to Encode the At-Most-One Constraint into SATProceedings of the 6th International Symposium on Information and Communication Technology10.1145/2833258.2833293(46-53)Online publication date: 3-Dec-2015
https://dl.acm.org/doi/10.1145/2833258.2833293
Escamocher GO'Sullivan B(2015)On the Minimal Constraint Satisfaction ProblemProceedings of the 9th International Conference on Combinatorial Optimization and Applications - Volume 948610.1007/978-3-319-26626-8_54(731-745)Online publication date: 18-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-319-26626-8_54
(2014)Structure-aware CNF obfuscation for privacy-preserving SAT solvingProceedings of the Twelfth ACM/IEEE Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2014.6961846(84-93)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1109/MEMCOD.2014.6961846
Gemelli NHudack JOh J(2013)Virtual Structure Reduction on Distributed K-Coloring ProblemsProceedings of the 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) - Volume 0210.1109/WI-IAT.2013.89(46-52)Online publication date: 17-Nov-2013
https://dl.acm.org/doi/10.1109/WI-IAT.2013.89
Arbelaez ACodognet P(2013)From sequential to parallel local search for SATProceedings of the 13th European conference on Evolutionary Computation in Combinatorial Optimization10.1007/978-3-642-37198-1_14(157-168)Online publication date: 3-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37198-1_14
Moreno-Scott JOrtíz-Bayliss JTerashima-Marín HConant-Pablos SMoore J(2012)Challenging heuristicsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330222(409-416)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330222
Anton C(2011)An improved satisfiable SAT generator based on random subgraph isomorphismProceedings of the 24th Canadian conference on Advances in artificial intelligence10.5555/2018192.2018197(44-49)Online publication date: 25-May-2011
https://dl.acm.org/doi/10.5555/2018192.2018197
Leyton-Brown KNudelman EShoham Y(2009)Empirical hardness modelsJournal of the ACM10.1145/1538902.153890656:4(1-52)Online publication date: 2-Jul-2009
https://dl.acm.org/doi/10.1145/1538902.1538906
Show More Cited By

Abstract

Cited By

Recommendations

Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden

Generating Instances for MAX2SAT with Optimal Solutions

Hidden gold in random generation of SAT satisfiable instances

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations