On forward checking for non-binary constraint satisfaction.

DOI10.1016/S0004-3702(02)00263-1MaRDI QIDQ1852854zbMATH OpenOpenAlexFDO

Authors P. Meseguer, Eugene C. Freuder, Javier Larrosa, Christian Bessiere

Publication date 21 January 2003

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0004-3702(02)00263-1, http://hdl.handle.net/10261/160964

zbMATH Keywords

Constraint satisfactionForward checkingNon-binary constraints

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Review text

Solving non-binary constraint satisfaction problems, a crucial challenge today, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical non-binary version, proposed by Van Hentenryck, is only one of these generalizations.

Recommendations

• On forward checking for non-binary constraint satisfaction
• Binary vs. non-binary constraints
• scientific article; zbMATH DE number 2243409
• scientific article; zbMATH DE number 2080297
• scientific article; zbMATH DE number 2086994

Cites work

• A theoretical evaluation of selected backtracking algorithms.
• Backtrack Programming
• scientific article; zbMATH DE number 2084696 (Why is no real title available?)

Cited in

(10)

• Combining restarts, nogoods and bag-connected decompositions for solving csps
• Partition search for non-binary constraint satisfaction
• Domain filtering consistencies for non-binary constraints
• A non-binary constraint ordering heuristic for constraint satisfaction problems
• Data optimizations for constraint automata
• Computing and restoring global inverse consistency in interactive constraint satisfaction
• Dealing with satisfiability and \(n\)-ary CSPs in a logical framework
• On forward checking for non-binary constraint satisfaction
• A compressed generalized hypertree decomposition-based solving technique for non-binary constraint satisfaction problems
• Integrating operations research in constraint programming

Describes a project that uses

Uses Software

• ILOG SCHEDULE

This page was built for publication: On forward checking for non-binary constraint satisfaction.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1852854)