CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Cost Propagation - Numerical Propagation for Optimization Problems

Birgit Grohe (Institutionen för data- och informationsteknik (Chalmers))
Göteborg : Chalmers University of Technology, 2007. - 42 s.

In this thesis, we investigate Cost Propagation, an approach to numerical propagation for optimization problems, where we combine ideas from both Constraint Programming and Combinatorial Optimization. We consider discrete optimization problems with binary variables that can be expressed in the model max_x sum_k g_k(x^k) where the terms g_k(x^k) are distinct arbitrary functions over subsets x^k of x. The problem is iteratively solved by propagation, i.e. by updates for single constraints or terms in the optimization model. We formalize a theory of updates in terms of equivalent problems with notions of consistency, local optimality, convergence and bounds, and with links to Linear Programming theory. We discuss some specific updates and analyse their behavior in propagation. Further, we introduce a special update, the non-conflicting update,that guarantees optimality if a solution is found by propagation. Finally, we perform computational experiments on three sample problems, the Assignment problem, a crossword puzzle and the Set Partitioning problem, illustrating advantages and limitations of the approach. The experiments also show that Cost Propagation can by itself solve non-trivial problems even without a top level search, which is otherwise needed to create a complete algorithm.

Nyckelord: Cost propagation, numerical propagation, optimization

Denna post skapades 2007-05-29.
CPL Pubid: 42246


Institutioner (Chalmers)

Institutionen för data- och informationsteknik (Chalmers)


Information Technology

Chalmers infrastruktur


Datum: 2007-06-19
Tid: 13:15
Lokal: EA, D&IT, Chalmers
Opponent: Dr. Per Kreuger, SICS, Stockholm

Ingår i serie

Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University 41L