Using Inference to Reduce Arc Consistency Computation

Bessiere, Christian; Freuder, Eugene C.; Régin, Jean-Charles

Using Inference to Reduce Arc Consistency Computation

Christian Bessière, Eugene C. Freuder, Jean-Charles Régin

Download BibTeX Cite

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 592-598.

Abstract

Constraint satisfaction problems are widely used in artificial intelligence. They involve finding values for problem variables subject to constraints that specify which combinations of values are consistent. Knowledge about properties of the constraints can permit inferences that reduce the cost of consistency checking. In particular, such inferences can be used to reduce the number of constraint checks required in establishing arc consistency, a fundamental constraint-based reasoning technique. A general AC-Inference schema is presented and various forms of inference discussed. A specific algorithm, AC-7, is presented, which takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other arc consistency algorithms perform. The effectiveness of this approach is demonstrated analytically, and experimentally on real-world problems.

Christian Bessiere, Eugene C. Freuder, and Jean-Charles Régin. 1995. Using Inference to Reduce Arc Consistency Computation. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95. IJCAI, 592–598. https://ijcai.org/proceedings/1995/78

@inproceedings{ijcai1995p78,
  title     = {Using Inference to Reduce Arc Consistency Computation},
  author    = {Bessiere, Christian and Freuder, Eugene C. and Régin, Jean-Charles},
  booktitle = {Proceedings of the Fourteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-95}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Chris S. Mellish},
  pages     = {592--598},
  year      = {1995},
  note      = {Constraint Satisfaction},
  url       = {https://ijcai.org/proceedings/1995/78},
}

TY  - CPAPER
TI  - Using Inference to Reduce Arc Consistency Computation
AU  - Bessiere, Christian
AU  - Freuder, Eugene C.
AU  - Régin, Jean-Charles
T2  - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1995
SP  - 592
EP  - 598
UR  - https://ijcai.org/proceedings/1995/78
ER  -