Balance and Filtering in Structured Satisfiable Problems

Kautz, Henry A.; Ruan, Yongshao; Achlioptas, Dimitris; Gomes, Carla P.; Selman, Bart; Stickel, Mark E.

Balance and Filtering in Structured Satisfiable Problems

Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 351-357.

Abstract

New methods to generate hard random problem instances have driven progress on algorithms for deduction and constraint satisfaction. Recently Achlioptas et al. (AAAI 2000) introduced a new generator based on Latin squares that creates only satisfiable problems, and so can be used to accurately test incomplete (one sided) solvers. We investigate how this and other generators are biased away from the uniform distribution of satisfiable problems and show how they can be improved by imposing a balance condition. More generally, we show that the generator is one member of a family of related models that generate distributions ranging from ones that are everywhere tractable to ones that exhibit a sharp hardness threshold. We also discuss the critical role of the problem encoding in the performance of both systematic and local search solvers.

Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, and Mark E. Stickel. 2001. Balance and Filtering in Structured Satisfiable Problems. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01. IJCAI, 351–357. https://ijcai.org/proceedings/2001/50

@inproceedings{ijcai2001p50,
  title     = {Balance and Filtering in Structured Satisfiable Problems},
  author    = {Kautz, Henry A. and Ruan, Yongshao and Achlioptas, Dimitris and Gomes, Carla P. and Selman, Bart and Stickel, Mark E.},
  booktitle = {Proceedings of the Seventeenth International Joint Conference on
               Artificial Intelligence, {IJCAI-01}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {351--357},
  year      = {2001},
  url       = {https://ijcai.org/proceedings/2001/50},
}

TY  - CPAPER
TI  - Balance and Filtering in Structured Satisfiable Problems
AU  - Kautz, Henry A.
AU  - Ruan, Yongshao
AU  - Achlioptas, Dimitris
AU  - Gomes, Carla P.
AU  - Selman, Bart
AU  - Stickel, Mark E.
T2  - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2001
SP  - 351
EP  - 357
UR  - https://ijcai.org/proceedings/2001/50
ER  -