Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Branching Constraint Satisfaction Problems for Solutions Robust under Likely Changes

David W. FowlerContact Information and Kenneth N. BrownContact Information

(5)  University of Aberdeen, Aberdeen, AB24 3UE, UK
Abstract
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.

Contact Information David W. Fowler
Email: dfowler@csd.abdn.ac.uk

Contact Information Kenneth N. Brown
Email: kbrown@csd.abdn.ac.uk
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)