Computer Science – Artificial Intelligence
Scientific paper
2009-09-24
Computer Science
Artificial Intelligence
Principles and Practice of Constraint Programming, 14th International Conference, CP 2008, Sydney, Australia, September 14-18,
Scientific paper
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in $O(n^2)$ time down a branch of the search tree. This improves upon the best existing domain consistency algorithm by a factor of $O(\log n)$. The flows used in these algorithms are derived from a linear program. Some of them differ from the flows used to propagate global constraints like GCC since the domains of the variables are encoded as costs on the edges rather than capacities. Such flows are efficient for maintaining bounds consistency over large domains and may be useful for other global constraints.
Maher Michael J.
Narodytska Nina
Quimper Claude-Guy
Walsh Toby
No associations
LandOfFree
Flow-Based Propagators for the SEQUENCE and Related Global Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Flow-Based Propagators for the SEQUENCE and Related Global Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flow-Based Propagators for the SEQUENCE and Related Global Constraints will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-425310