Anticipatory pruning networks and forward checking in CLP over continuous domains

摘要

In this paper, the notion of the Anticipatory Pruning Network (APN) is introduced and developed for the propositional part of the 2LP system; 2LP (Linear Programming and Logic Programming) is a constraint logic programming system which has been developed and implemented at the Logic Based System Lab at Brooklyn College/CUNY. Using the compilation of rules in the style of the Rete algorithm, the APN maps program clauses into a network. The APN prunes a search space by consistency checking and inconsistency propagation through the network and resets itself upon backtracking. The APN extends forward checking to continuous constraint domains. Overall, the benchmarks show the APN to be an effective forward checking mechanism for both discrete and continuous problem domains for Simplex based constraint solvers. In particular, the APN is an effective pruning method for constrained mixed integer, linear optimization problems.