|Date: Friday, November 17, 2017
Location: 1084 East Hall (3:00 PM to 4:00 PM)
Title: Analysis of countably-infinite linear programming problems and simplex-type 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 well-understood, and several effective algorithms for their solution have been widely studied and implemented. Countably-Infinite 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 pre-specified 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 finite-dimensional LPs, including challenges (and some successes) in implementing it.
Speaker: Marina Epelman
Institution: University of Michigan, Industrial and Operations Engineering
Event Organizer: John Schotland firstname.lastname@example.org