Constraint propagation as information maximization

DOI10.1016/J.ARTINT.2013.02.002zbMATH Open1270.68264arXiv1201.5426OpenAlexW2003757888MaRDI QIDQ360048FDOQ360048

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

Publication date: 23 August 2013

Published in: Artificial Intelligence (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1201.5426

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

Mathematics Subject Classification ID

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

Cites Work

• Design, implementation, and evaluation of the constraint language cc(FD)
• Consistency in networks of relations
• Principles of Constraint Programming
• Newton: Constraint programming over nonlinear constraints
• The essence of constraint propagation
• Chaotic relaxation
• Interval arithmetic: from principles to implementation
• Applying interval arithmetic to real, integer, and boolean constraints
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

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

Uses Software

• COMET
• Newton
• cc(FD)

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)