Advertisement
Published in:
2008 | OriginalPaper | Chapter
Cost Propagation – Numerical Propagation for Optimization Problems
Authors : Birgit Grohe, Dag Wedelin
Published in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We investigate
cost propagation
for solving combinatorial optimization problems with finite domain variables, expressed as an additive component model. Cost propagation combines ideas from both constraint programming and integer programming into a single approach, where problems are iteratively solved by numerical propagation, with updates for single constraint terms in the component model.
We outline a theory of propagation in terms of equivalent problems with notions of consistency, local optimality, convergence and bounds. We define several different updates and analyze their properties.
Finally, we outline computational experiments on the simple assignment problem, the set partitioning problem, and a crossword puzzle. The experiments illustrate that even without a top level search, cost propagation can by itself solve non-trivial problems, and also be attractive compared to standard methods.