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.