Date: Friday, November 17, 2017
Location: 1084 East Hall (3:00 PM to 4:00 PM)
Title: Analysis of countablyinfinite linear programming problems and simplextype algorithms
Abstract: Linear Programming (LP) optimization problems, where a linear function on R^n is minimized subject to, say, m linear constraints on the variables, are the workhorse of Operations Research, used as a modeling tool in a vast variety of applications. Nor surprisingly, their mathematical properties are wellunderstood, and several effective algorithms for their solution have been widely studied and implemented. CountablyInfinite Linear Programs (CILPs), i.e., linear programs where the number of variables and constraints is countably infinite, are also useful in modeling  especially in applications that involve decision making over time, with no prespecified horizon. However, they are challenging to analyze or solve, since useful properties of finite LPs often fail to extend to general CILPs. In this talk, I'll survey some work on structured CILPs, which do posess some of these properties, including duality, complementary slackness, and a simple analytical representation of extreme points. In addition, I'll discuss an algorithmic approach for solving such CILPs inspired by the simplex method for finitedimensional LPs, including challenges (and some successes) in implementing it.
Files:
Speaker: Marina Epelman
Institution: University of Michigan, Industrial and Operations Engineering
Event Organizer: John Schotland jcsch@umich.edu
