TITLE: Countably infinite linear programs: theory, algorithms, and applications

SPEAKER: Archis Ghate

ABSTRACT:

We will consider linear programs (LPs) with a countably infinite number of variables and a countably infinite number of constraints. These countably infinite linear programs (CILPs) arise in several applications including countable state Markov decision processes (MDPs), infinite-stage minimum cost network flow problems, and non-stationary infinite-horizon planning problems. Standard results, intuition, and interpretations from finite-dimensional LPs may not extend to CILPs. For example, weak and strong duality may not hold, extreme points may not be equivalent to basic feasible solutions, dual variables may not have a shadow price interpretation, and a finitely implementable Simplex algorithm is not known. In this talk, we will explore sufficient conditions under which such theoretical results and algorithms can be developed for CILPs. Several examples and counterexamples will be discussed to explain key ideas. Non-stationary infinite-horizon MDPs will be employed as a flagship example where everything works out nicely. Time permitting, an inverse optimization framework and a robust optimization approach for CILPs will be presented briefly.

 Speaker bio:  Archis Ghate is an Associate Professor of Industrial and Systems Engineering at the University of Washington in Seattle. His research focuses on stochastic and dynamic optimization. Archis received a PhD from the University of Michigan in 2006, an MS from Stanford University in 2003, and completed his undergraduate education at the Indian Institute of Technology, Bombay in 2001. He is a recipient of the NSF CAREER award and the award for Excellence in Teaching OR from the Institute of Industrial Engineers. His doctoral students have won the Dantzig dissertation award and the Bonder scholarship from INFORMS, as well as other competitive awards from the University of Washington.