A strong local consistency for constraint satisfaction | IEEE Conference Publication | IEEE Xplore

A strong local consistency for constraint satisfaction


Abstract:

Filtering techniques are essential for efficient solution searching in a constraint network (CN). However, for a long time, it has been considered that to efficiently red...Show More

Abstract:

Filtering techniques are essential for efficient solution searching in a constraint network (CN). However, for a long time, it has been considered that to efficiently reduce the search space, the best choice is the limited local consistency achieved by forward checking. However, more recently, it has been shown that maintaining arc consistency (which is a more pruningful local consistency) during searching outperforms forward checking on hard and large constraint networks. In this paper, we show that maintaining a local consistency which is stronger than arc consistency during searching can be advantageous. According to a comparison of local consistencies that are more pruningful than the arc consistency which can be used on large CNs, max-restricted path consistency (Max-RPC) is one of the most promising local consistencies. We propose a new local consistency, called Max-RPCEn (Max-RPC Enhanced), that is stronger than Max-RPC and that has almost the same CPU time requirements.
Date of Conference: 09-11 November 1999
Date Added to IEEE Xplore: 06 August 2002
Print ISBN:0-7695-0456-6
Print ISSN: 1082-3409
Conference Location: Chicago, IL, USA

Contact IEEE to Subscribe

References

References is not available for this document.