TY - GEN
T1 - Branching constraint satisfaction problems for solutions robust under likely changes
AU - Fowler, David W.
AU - Brown, Kenneth N.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - Many applications of CSPs require partial solutions to be found before all the information about the problem is available. We examine the case where the future is partially known, and where it is important to make decisions in the present that will be robust in the light of future events. We introduce the branching CSP to model these situations, incorporating some elements of decision theory, and describe an algorithm for its solution that combines forward checking with branch and bound search. We also examine a simple thresholding method which can be used in conjunction with the forward checking algorithm, and we show the trade-off between time and solution quality.
AB - Many applications of CSPs require partial solutions to be found before all the information about the problem is available. We examine the case where the future is partially known, and where it is important to make decisions in the present that will be robust in the light of future events. We introduce the branching CSP to model these situations, incorporating some elements of decision theory, and describe an algorithm for its solution that combines forward checking with branch and bound search. We also examine a simple thresholding method which can be used in conjunction with the forward checking algorithm, and we show the trade-off between time and solution quality.
UR - https://www.scopus.com/pages/publications/84945971544
U2 - 10.1007/3-540-45349-0_38
DO - 10.1007/3-540-45349-0_38
M3 - Conference proceeding
AN - SCOPUS:84945971544
SN - 3540410538
SN - 9783540410539
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 500
EP - 504
BT - Principles and Practice of Constraint Programming - CP 2000 - 6th International Conference, CP 2000, Proceedings
A2 - Dechter, Rina
PB - Springer Verlag
T2 - 6th International Conference on Principles and Practice of Constraint Programming, CP2000
Y2 - 18 September 2000 through 21 September 2000
ER -