Back to activities
DS4DM Coffee Talk

On the solution of pseudo-polynomial dynamic programs involving large magnitudes


Aug 14, 2023   11:00 AM — 12:00 PM

Claudio Contardo Associate Professor, Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Canada

Claudio Contardo

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.

Federico Bobbio organizer
Defeng Liu organizer
Léa Ricard organizer


Hybrid activity at GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4

Associated organization