Title of Presentation: Solving Hard Shortest Path Problems with the Pulse Framework

Abstract:

Many challenging applications in the field of transportation and logistics often involve the solution of underlying large-scale network problems with shortest path structures. The pulse framework implements ideas and strategies that have been available in the playground of network optimization for years, but when used collectively under a single framework they become stronger and are able to solve a wide array of hard shortest path problems. Initially, we proposed the pulse algorithm as an exact method for solving shortest paths with side constraints. Later, we identified other shortest path variants where the same principle behind the pulse algorithm applied. In this tutorial, we present the pulse algorithm as a framework based on the idea of performing an implicit enumeration of the entire solution space supported by pruning strategies that efficiently discard a vast number of solutions. We focus on the key aspects that have made possible the effective solution of several shortest path variants. We also illustrate the use of the pulse algorithm as a building block to solve hard combinatorial problems beyond the shortest path domain.

Bio

Andres L. Medaglia is Professor of Industrial Engineering at Universidad de los Andes (Bogotá, Colombia) and director of the research center Centro para la Optimización y Probabilidad Aplicada (COPA). He holds a Ph.D. (2001) in Operations Research (OR) from North Carolina State University (USA). From 1999 to 2002 he worked as an optimization specialist developing decision support systems for SAS (Cary, NC, USA). In 2002, he joined the Industrial Engineering Department at Universidad de los Andes. His current research interests include the development and application of optimization techniques to transportation and logistics, health systems, agricultural systems, and engineering design. He has served as Secretary and Vicepresident of the Latin-Ibero American Association of Operations Research (ALIO); as Vicepresident of Central/South America for the Institute of Industrial Engineers (IIE); and as Vicepresident of the Colombian Operational Research Society (ASOCIO). In INFORMS, he served as the Liason for the Americas and in the Best Paper Award Committee for the Transportation Science & Logistics Society (TSL). He has been the recipient of several prizes, most recently, the INFORMS/TSL President’s Service Award (2017), the IFORS Prize for OR in Development (Quebec City, Canada, 2017), the first prize in the INFORMS Railway Application Section (RAS) Problem Solving Competition (2011), and the EURO Award for the Best EJOR (Review) Paper in 2015. More information at: http://wwwprof.uniandes.edu.co/~amedagli