Implementing dynamic programming recurrences in constraint handling rules with rule priorities

Ahmed Magdy, Frank Raiser, and Thom Frühwirth. Implementing dynamic programming recurrences in constraint handling rules with rule priorities. 2010, 24th Workshop on (Constraint) Logic Programming, Workshop

Abstract:

Dynamic Programming (DP) is an important technique used in solving optimization problems. A close correspondence between DP recurrences and Constraint Handling Rules with rule priorities (CHRrp) yields natural implementations of DP problems in CHRrp. In this work, we evaluate different implementation techniques with respect to their runtime. From our results we derive a set of guidelines for implementing arbitrary DP problems in CHRrp.