[Back]

C. Bacher, G. Raidl:
"Integrating Algebraic Dynamic Programming in Combinatorial Optimization";
Talk: Austrian Workshop on Metaheuristics, Graz; 2016-12-02.

Although Dynamic Programming is a fundamental technique in the field of combinatorial optimization, the traditional take on the method is an exemplary one.
Whereas other techniques like Integer Programming or Constraint Programming possess clearly defined semantics, frameworks and solvers, Dynamic Programming code is usually handcrafted to single problem.
Algebraic Dynamic Programming (ADP) (Giegerich et al., 2002) is a promising approach to provide these things for Dynamic Programming.
In ADP dynamic programs are expressed as context free grammars to describe the search space of the problem as a form of object composition/decomposition and use separate evaluation algebras to evaluate objects of the search space.
Originally developed for the bioinformatics community ADP was restricted to sequence data (strings) and has since been extended to set/general data structures in (Siederdissen et al., 2014) and (Siederdissen et al., 2015).

Nevertheless, to use ADP in day-to-day combinatorial problems often a more expressive form of modelling is needed.
We therefore develop a new Algebraic Dynamic Programming Framework called \emph{Whistle} which intends to make ADP more useful to the general combinatorial optimization and operations research communities.
The presented work will focus on modelling classical DP problems by means of ADP, as well as introduce new useful features like explicit indexed grammars, index propagators, index amalgamation, search engines, and partial invalidation to broaden the applicability of ADP.

http://publik.tuwien.ac.at/files/publik_256159.pdf