Sparse Matrix Techniques
Marc Pouly, Jürg Kohlas · 2011
This chapter gives a more rigorous definition of solutions in the context of valuation algebras and derives some basic properties. It then presents different algorithms for the construction of single solutions or complete solution sets. These methods are again generic and can be applied to all valuation algebras with a suitable notion of solution. A particular important field of application is constraint reasoning or the solution of optimization problems. The chapter shows that these problems emerge from a particular subclass of the family of semiring valuation algebras. In fact, executing the fusion or bucket elimination algorithm for the computation of a marginal of an optimization problem and applying the generic solution construction procedure presented in the chapter coincides with a well-known programming paradigm called dynamic programming. The chapter therefore is seen as a generalization of both approaches from constraint systems to arbitrary valuation algebras with solutions. Controlled Vocabulary Terms dynamic programming; optimisation