Presentation on YouTube.

In this presentation, we will introduce an iterative algorithm for the exact solution of dynamic programs of pseudo-polynomial complexity, especially useful when large magnitudes are involved. Our method iterates between the solution of a dynamic program on a loser dimensional space providing a dual approximation, and of a refinement procedure used to achieve primal feasibility. We illustrate our method on three problems relevant in practice: the ranged subset-sum problem, the tree partitioning problem, and the shortest path problem with waiting costs. We show that the proposed method is capable of providing significant speedups over classical implementations of dynamic programming.

Biography: Claudio Contardo is an Associate Professor of Operations Research at the Department of Mechanical, Industrial and Aerospace Engineering at Concordia University (since 2022). Before joining Concordia, he was a Software Scientist at IBM CPLEX (2021-2022) and an Associate Professor of Business Administration at UQAM, Canada (2012-2020). He is the author of more than 20 scientific articles in the areas of mathematical programming, vehicle routing, and location analysis. He serves as an Associate Editor of ITOR since 2019.