### Skapa referens, olika format (klipp och klistra)

**Harvard**

Grohe, B. (2007) *Cost Propagation - Numerical Propagation for Optimization Problems*. Göteborg : Chalmers University of Technology (Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, nr: 41L).

** BibTeX **

@book{

Grohe2007,

author={Grohe, Birgit},

title={Cost Propagation - Numerical Propagation for Optimization Problems},

abstract={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.},

publisher={Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola,},

place={Göteborg},

year={2007},

series={Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: 41L},

keywords={Cost propagation, numerical propagation, optimization},

note={42},

}

** RefWorks **

RT Dissertation/Thesis

SR Print

ID 42246

A1 Grohe, Birgit

T1 Cost Propagation - Numerical Propagation for Optimization Problems

YR 2007

AB 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.

PB Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola,

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

LA eng

OL 30