Forbidding solutions in (integer) linear programming

ACO Student Seminar
Wednesday, January 23, 2013 - 12:00
1 hour (actually 50 minutes)
ISyE Executive classroom
Georgia Tech ISyE
In this talk we consider the problem of finding basic solutions to linear programs where some vertices are excluded. We study the complexity of this and related problems, most of which turn out to be hard. On the other hand, we show that forbidding vertices from 0-1 polytopes can be carried out with a compact extended formulation. A similar result holds for integer programs having a box-integrality property. We discuss some applications of our results.