ITE: A Lightweight Implementation of Stratified Reasoning for Constructive Logical Operators
This work addresses a specific bottleneck in Constraint Programming for users needing expressive logical operators, though it is incremental as it builds on existing methods without achieving SOTA performance.
The paper tackles the difficulty of handling logical connectors with constructive information in Constraint Programming by introducing ITE, a lightweight implementation of stratified constructive reasoning, which is shown to be more efficient than generic approaches for logical constraint systems over finite domains.
Constraint Programming (CP) is a powerful declarative programming paradigm where inference and search are interleaved to find feasible and optimal solutions to various type of constraint systems. However, handling logical connectors with constructive information in CP is notoriously difficult. This paper presents If Then Else (ITE), a lightweight implementation of stratified constructive reasoning for logical connectives. Stratification is introduced to cope with the risk of combinatorial explosion of constructing information from nested and combined logical operators. ITE is an open-source library built on top of SICStus Prolog clp(fd), which proposes various operators, including constructive disjunction and negation, constructive implication and conditional. These operators can be used to express global constraints and to benefit from constructive reasoning for more domain pruning during constraint filtering. Even though ITE is not competitive with specialized filtering algorithms available in some global constraints implementations, its expressiveness allows users to easily define well-tuned constraints with powerful deduction capabilities. Our extended experimental results show that ITE is more efficient than available generic approaches that handle logical constraint systems over finite domains.