Using Auxiliary Variables and Implied Constraints to Model Non-Binary Problems
Abstract
We perform an extensive theoretical and empirical analysis of the use of auxiliary variables and implied constraints in modelling a class of non-binary constraint satisfaction problems called problems of distance. This class of problems include 1-d, 2-d and circular Golomb rulers. We identify a large number of different models, both binary and non-binary, and compare theoretically the level of consistency achieved by generalized arc consistency on them. Our experiments show that the introduction of auxiliary variables and implied constraints can significantly reduce the size of the search space. For instance, our final models reduce the time to find an optimal 10-mark Golomb ruler 50-fold.
Cite
Text
Smith et al. "Using Auxiliary Variables and Implied Constraints to Model Non-Binary Problems." AAAI Conference on Artificial Intelligence, 2000.Markdown
[Smith et al. "Using Auxiliary Variables and Implied Constraints to Model Non-Binary Problems." AAAI Conference on Artificial Intelligence, 2000.](https://mlanthology.org/aaai/2000/smith2000aaai-using/)BibTeX
@inproceedings{smith2000aaai-using,
title = {{Using Auxiliary Variables and Implied Constraints to Model Non-Binary Problems}},
author = {Smith, Barbara M. and Stergiou, Kostas and Walsh, Toby},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2000},
pages = {182-187},
url = {https://mlanthology.org/aaai/2000/smith2000aaai-using/}
}