Student: Andres Iroume

Title:  Sparsity in Integer Programming

Advisors:  Dr. Santanu Dey

Committee Members: Dr. Marco Molinaro (PUC Rio), Dr. David Goldsman, Dr. Alejandro Toriello and Dr. Andy Sun.

Date and time:  Monday, December 12, 2016, noon (EST)

Location:  Groseclose

Abstract: This thesis deals with understanding the effect of sparsity in integer programming. Chapter 1 corresponds to the introduction and outlay of the thesis, Chapter 2 deals with approximating polytopes using sparse cuts under various settings. Chapter 3 discusses a variant on feasibility pump that automatically detects and harnesses sparsity. Chapter 4 deals with the ratio of the number of integral extreme points to the total number of extreme points for a family of random polytopes. Chapter 5 discusses the strength of multi-row aggregation cuts in the context of sign- pattern integer programs (IPs).