Bounded Search and Symbolic Inference for Constraint Optimization
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 286-290.
Abstract
Constraint optimization underlies many problems in AI. We present a novel algorithm for finite domain constraint optimization that generalizes branch-and-bound search by reasoning about sets of assignments rather than individual assignments. Because in many practical cases, sets of assignments can be represented implicitly and compactly using symbolic techniques such as decision diagrams, the set-based algorithm can compute bounds faster than explicitly searching over individual assignments, while memory explosion can be avoided by limiting the size of the sets. Varying the size of the sets yields a family of algorithms that includes known search and inference algorithms as special cases. Furthermore, experiments on random problems indicate that the approach can lead to significant performance improvements.
@inproceedings{ijcai2005p211,
title = {Bounded Search and Symbolic Inference for Constraint Optimization},
author = {Sachenbacher, Martin and Williams, Brian C.},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {286--290},
year = {2005},
url = {https://ijcai.org/proceedings/2005/211},
}
TY - CPAPER TI - Bounded Search and Symbolic Inference for Constraint Optimization AU - Sachenbacher, Martin AU - Williams, Brian C. T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 286 EP - 290 UR - https://ijcai.org/proceedings/2005/211 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
