The Complexity of Cutting Plane Methods for Random Integer Programs

Karthekeyan Chandrasekaran, CS/ACO (mentor: Santosh Vempala, CS) -It is noticeable that among Karp's 21 NP-complete problems, the integer programming problem is one that lacks understanding under the probabilistic input setting. I would like to initiate this study and fi nd a reasonable probability distribution under which one can have a polynomial time cutting plane procedure. I would like to understand if there exists a natural distribution on the constraint matrix Ax<=b and the objective direction c, for which the cutting plane method converges to an integer optimum in polynomial time.