zbMATH — the first resource for mathematics

Decision diagrams and dynamic programming. (English) Zbl 1382.90113
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 94-110 (2013).
Summary: Binary and multivalued decision diagrams are closely related to dynamic programming (DP) but differ in some important ways. This paper makes the relationship more precise by interpreting the DP state transition graph as a weighted decision diagram and incorporating the state-dependent costs of DP into the theory of decision diagrams. It generalizes a well-known uniqueness theorem by showing that, for a given optimization problem and variable ordering, there is a unique reduced weighted decision diagram with “canonical” edge costs. This can lead to simplification of DP models by transforming the costs to canonical costs and reducing the diagram, as illustrated by a standard inventory management problem. The paper then extends the relationship between decision diagrams and DP by introducing the concept of nonserial decision diagrams as a counterpart of nonserial dynamic programming.
For the entire collection see [Zbl 1263.68017].

90C39 Dynamic programming
68P05 Data structures
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B05 Inventory, storage, reservoirs
Full Text: DOI