Constraint and Variable Ordering Heuristics for Compiling Configuration Problems
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 149-153.
Abstract
To facilitate interactive design, the solutions to configuration problems can be compiled into a decision diagram. We develop three heuristics for reducing the time and space required to do this. These heuristics are based on the distinctive clustered and hierarchical structure of the constraint graphs of configuration problems. The first heuristic attempts to limit the growth in the size of the decision diagram by providing an order in which constraints are added to the decision diagram. The second heuristic provides an initial order for the variables within the decision diagram. Finally, the third heuristic groups variables together so that they can be reordered by a dynamic variable reordering procedure used during the construction of the decision diagram. These heuristics provide one to two orders magnitude improvement in the time to compile a wide range of configuration.
@inproceedings{ijcai2007p22,
title = {Constraint and Variable Ordering Heuristics for Compiling Configuration Problems},
author = {Narodytska, Nina and Walsh, Toby},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {149--153},
year = {2007},
url = {https://ijcai.org/proceedings/2007/22},
}
TY - CPAPER TI - Constraint and Variable Ordering Heuristics for Compiling Configuration Problems AU - Narodytska, Nina AU - Walsh, Toby T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 149 EP - 153 UR - https://ijcai.org/proceedings/2007/22 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
