P.C. Rossin College of
Engineering and Applied Science

Upcoming Events

INDUSTRIAL AND SYSTEMS ENGINEERING SEMINAR SERIES

Title: Fully Polynomial-Time Approximation Schemes for Stochastic Dynamic Programs: Theory and Applications

Speaker: Giacomo Nannicini, IBM T. J. Watson Research Center
 
Time & Location:
Tuesday, January 29, 2019
4:00-5:00pm
Mohler Lab, #453

Abstract      

This talk presents some recent results in our quest to build approximation algorithms for stochastic dynamic programs that are both theoretically and computationally efficient. The main constructive result is an FPTAS for dynamic programs with scalar state, polyhedral action spaces, convex costs and linear transition functions. The random variables are assumed to be described compactly by an oracle to their CDFs. This type of problem finds applications in the area of optimal planning under uncertainty, and can be thought of as the problem of optimally managing a single non-discrete resource over a finite time horizon.

We show that under a value oracle model for the cost functions this result for one-dimensional state space is “best possible”, because a similar dynamic programming model with two-dimensional state space does not admit a PTAS. Along the way, we will discuss hardness results regarding the inapproximability of certain two-dimensional convex functions, and, if time permits, applications to a newsvendor model. The talk is based on joint work with Nir Halman.

Bio sketch

Giacomo Nannicini is a Research Staff Member in the Theory of Quantum Computing and Information group at the IBM T. J. Watson Research Center. Before joining IBM, he was an assistant professor in the Engineering Systems and Design pillar at the Singapore University of Technology and Design. His main research interest is optimization broadly defined and its applications. Giacomo received several awards, including the 2016 COIN-OR Cup, the 2015 Robert Faure prize, the 2012 Glover-Klingman prize. His algorithms and software are used by one of the largest real-time traffic and mobility information groups in Europe, and by IBM's Cloud AI service.

 

 
Tuesday, April 2, 2019  - 4:00p.m.
INFORMS Chapter Distinguished Speaker Series - Stefan Wild, Argonne National Lab
 
Tuesday, March 19, 2019 - 4:00p.m.
ISE Seminar Series - William K. Klimack, Chevron
 
Tuesday, March 5, 2019 - 4:00p.m.
ISE Seminar Series - James Luedtke, University of Wisconsin-Madison
 
Tuesday, February 12, 2019 - 4:00p.m.
ISE Seminar Series - J. Cole Smith, Clemson University

 


Past Events

Spring 2019

 

Fall 2018
Tuesday, December 4, 2018 - 4:00pm
ISE Seminar Series - Andreas Wächter, Northwestern University
"Nonlinear Programming Formulations of Chance-Constraints"
 
Tuesday, November 27, 2018 - 4:00pm
INFORMS Chapter Distinguished Speaker Series - Gerard Cornuejols, Carnegie Mellon University
"Packing and Covering"
 
Tuesday, November 13, 2018 - 4:00pm
ISE Seminar Series - Mert Gürbüzbalaban, Rutgers University
"Momentum Acceleration Under Random Gradient Noise: From Convex to Non-Convex Optimization"
 
Tuesday, October 30, 2018 - 4:00pm
ISE Seminar Series - Michael Katehakis, Rutgers University
"Reinforcement Learning: Connections Between MDPs and MAB Problems"
 
Tuesday, October 2, 2018 - 4:00pm
ISE Seminar Series - Michael L. Overton, Courant Institute of Mathematical Sciences, NYU
"Nonsmooth, Nonconvex Optimization: Algorithms and Examples"
 
Spring 2018
 
Tuesday, May 8, 2018 - 4:00pm
ISE Seminar Series - Krzysztof Choromanski, Google
"Structure is all that you need - Learning Compressed RL Policies Via Orthogonal Gradient Sensing"
 
Tuesday, May 1, 2018 - 4:00pm
ISE Seminar Series - Henry Lam, Columbia University
"Assessing Solution Quality in Stochastic Optimization with Limited Data"
 
Tuesday, April 24, 2018 - 4:00pm
INFORMS Chapter Distinguished Speaker Series - James Renegar, Cornell University
"A Simple Nearly-Optimal Restart Scheme for Speeding-Up First Order Methods"
 
Thursday, April 19, 2018 - 4:00pm
ISE Seminar Series - Matthias Walter, RWTH Aachen University
"Investigating Polyhedra by Oracles"
 
Tuesday, April 10, 2018 - 4:00pm
ISE Seminar Series - Stefano Coniglio, University of Southampton
"Network Routing Through the Internet as a Stackelberg Game"
 
Tuesday, March 6, 2018 - 4:00pm
ISE Seminar Series - Bo Zeng, University of Pittsburgh
"Robust and Chance Constrained Optimization in Power and Logistics Systems"
 
Fall 2017
 
Tuesday, December 5, 2017 - 4:00pm
ISE Seminar Series - Garud Iyengar, Columbia University
"Automatic Event Detection in Basketball"
 
Thursday, November 30, 2017 - 4:00pm
Spencer C. Schantz Technical Lecture - William J. Cook, University of Waterloo
"Guiding the Cutting-Plane Method"
 
Wednesday, November 29, 2017 - 4:00pm
Spencer C. Schantz Distinguished Lecture Series Presents William J. Cook
"In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation"
 
Tuesday, November 14, 2017 - 4:00pm
ISE Seminar Series - Jonathan Eckstein, Rutgers University
"Asynchronous Projective Splitting for Convex Optimization and Monotone Inclusion Problems"
 
Tuesday, November 7, 2017 - 4:00pm
ISE Seminar Series - Osman Y. Ozaltin, North Carolina State University
"A Branch-and-cut Algorithm for Discrete Bilevel Linear Programs"
 
Tuesday, October 31, 2017 - 4:00pm
ISE Seminar Series - Oleg Prokopyev, University of Pittsburgh
"Sequential Max-Min Bilevel Linear Programming with Incomplete Information and Learning"
 
Tuesday, October 10, 2017 - 4:00pm
ISE Seminar Series - Ion Necoara, University Politehnica of Bucharest
"Conditions for Linear Convergence of (Stochastic) First Order Methods"
 
Thursday, October 5, 2017 - 4:00pm
INFORMS Chapter Distinguished Speaker Series: Nick Trefethen, University of Oxford
 
Tuesday, September 26, 2017 - 4:00pm
ISE Seminar Series - Andrew Dorsett, Wolfram Research
"Mathematica 11 in Education and Research"
 
Tuesday, September 19, 2017 - 4:00pm
ISE Seminar Series - Alejandro Ribeiro, University of Pennsylvania
"High Order Methods in Empirical Risk Minimization"
 
Tuesday, August 22, 2017 - 4:00pm
ISE Seminar Series - Giorgio Fasano, Thales Alenia Space
"Solving Non-Standard Packing Problems by Global Optimization and Heuristics"