event
ISyE Seminar - Laurence Wolsey
Primary tabs
TITLE: Projection of Shortest Path Extended Formulations
ABSTRACT:
Several important subproblems, such as switching machines on and off, finding an optimal convex set in 2-D, or buying and selling of a commodity, can be formulated as shortest/longest path problems in an acyclic graph. The corresponding polyhedron provides an implicit polynomial size description of the convex hull of solutions. A natural question is whether one can find a similar description in the original variables of the problem. In this talk we present several examples, each time using a different technique to obtain the projection. This is in large part joint work with Maurice Queyranne.
Status
-
Workflow Status:
Published -
Created By:
Anita Race -
Created:
11/07/2016 -
Modified By:
Fletcher Moore -
Modified:
04/13/2017
Categories
Keywords
Target Audience