TY - GEN

T1 - Filtering numerical CSPs using well-constrained subsystems

AU - Araya, Ignacio

AU - Trombettoni, Gilles

AU - Neveu, Bertrand

PY - 2009

Y1 - 2009

N2 - When interval methods handle systems of equations over the reals, two main types of filtering/contraction algorithms are used to reduce the search space. When the system is well-constrained, interval Newton algorithms behave like a global constraint over the whole n ×n system. Also, filtering algorithms issued from constraint programming perform an AC3-like propagation loop, where the constraints are iteratively handled one by one by a revise procedure. Applying a revise procedure amounts in contracting a 1 ×1 subsystem. This paper investigates the possibility of defining contracting well-constrained subsystems of size k (1≤ k ;≤ n). We theoretically define the Box-k-consistency as a generalization of the state-of-the-art Box-consistency. Well-constrained subsystems act as global constraints that can bring additional filtering w.r.t. interval Newton and 1 ×1 standard subsystems. Also, the filtering performed inside a subsystem allows the solving process to learn interesting multi-dimensional branching points, i.e., to bisect several variable domains simultaneously. Experiments highlight gains in CPU time w.r.t. state-of-the-art algorithms on decomposed and structured systems.

AB - When interval methods handle systems of equations over the reals, two main types of filtering/contraction algorithms are used to reduce the search space. When the system is well-constrained, interval Newton algorithms behave like a global constraint over the whole n ×n system. Also, filtering algorithms issued from constraint programming perform an AC3-like propagation loop, where the constraints are iteratively handled one by one by a revise procedure. Applying a revise procedure amounts in contracting a 1 ×1 subsystem. This paper investigates the possibility of defining contracting well-constrained subsystems of size k (1≤ k ;≤ n). We theoretically define the Box-k-consistency as a generalization of the state-of-the-art Box-consistency. Well-constrained subsystems act as global constraints that can bring additional filtering w.r.t. interval Newton and 1 ×1 standard subsystems. Also, the filtering performed inside a subsystem allows the solving process to learn interesting multi-dimensional branching points, i.e., to bisect several variable domains simultaneously. Experiments highlight gains in CPU time w.r.t. state-of-the-art algorithms on decomposed and structured systems.

UR - http://www.scopus.com/inward/record.url?scp=70350430732&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04244-7_15

DO - 10.1007/978-3-642-04244-7_15

M3 - Conference contribution

AN - SCOPUS:70350430732

SN - 3642042430

SN - 9783642042430

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 172

BT - Principles and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings

T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009

Y2 - 20 September 2009 through 24 September 2009

ER -