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