Constraint propagation as information maximization

DOI10.1016/J.ARTINT.2013.02.002MaRDI QIDQ360048zbMATH OpenOpenAlexFDO

Authors A. Nait Abdallah, M. H. van Emden

Publication date 23 August 2013

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5426, http://www.sciencedirect.com/science/article/pii/S0004370213000210

Mathematics Subject Classification ID

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

Abstract: This paper draws on diverse areas of computer science to develop a unified view of computation: (1) Optimization in operations research, where a numerical objective function is maximized under constraints, is generalized from the numerical total order to a non-numerical partial order that can be interpreted in terms of information. (2) Relations are generalized so that there are relations of which the constituent tuples have numerical indexes, whereas in other relations these indexes are variables. The distinction is essential in our definition of constraint satisfaction problems. (3) Constraint satisfaction problems are formulated in terms of semantics of conjunctions of atomic formulas of predicate logic. (4) Approximation structures, which are available for several important domains, are applied to solutions of constraint satisfaction problems. As application we treat constraint satisfaction problems over reals. These cover a large part of numerical analysis, most significantly nonlinear equations and inequalities. The chaotic algorithm analyzed in the paper combines the efficiency of floating-point computation with the correctness guarantees of arising from our logico-mathematical model of constraint-satisfaction problems.

Recommendations

• Constrained information maximization by free energy minimization
• scientific article; zbMATH DE number 370484
• scientific article; zbMATH DE number 1234564
• The essence of constraint propagation
• scientific article; zbMATH DE number 5885078
• General-purpose optimization through information maximization
• Measures of Information in Generalized Constraints
• An information-based neural approach to constraint satisfaction
• scientific article; zbMATH DE number 1487973
• Propagating belief functions through constraint systems

Cites work

• scientific article; zbMATH DE number 3440003 (Why is no real title available?)
• scientific article; zbMATH DE number 3043879 (Why is no real title available?)
• Applying interval arithmetic to real, integer, and boolean constraints
• Chaotic relaxation
• Consistency in networks of relations
• Design, implementation, and evaluation of the constraint language cc(FD)
• Interval arithmetic: from principles to implementation
• Newton: Constraint programming over nonlinear constraints
• Principles of Constraint Programming
• The essence of constraint propagation

Cited in

(2)

• Principles and Practice of Constraint Programming – CP 2004
• Constraint propagation, relational arithmetic in AI systems and mathematical programs

Describes a project that uses

Uses Software

• cc(FD)
• Newton
• COMET

This page was built for publication: Constraint propagation as information maximization

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