Show simple item record

dc.contributor.advisorDey, Santanu
dc.contributor.authorIroume, Andres
dc.date.accessioned2017-06-07T17:38:41Z
dc.date.available2017-06-07T17:38:41Z
dc.date.created2017-05
dc.date.issued2017-01-11
dc.date.submittedMay 2017
dc.identifier.urihttp://hdl.handle.net/1853/58207
dc.description.abstractSparse input data is data in which most of the data coefficients are zero. Many areas of scientific computing and optimization have been very successful in harnessing the effect of sparsity of input data to improve the efficacy of algorithms. Surprisingly, the use of sparsity of input data is a very under explored direction of research in the context of Integer Programming. Harnessing the sparsity present in the underlying linear relaxation, using decomposition/reformulation techniques and complexity results for approximation algorithms correspond to most of the previous results in this area. In this thesis, we deal with understanding the effect of sparsity in Integer Programming. We study how to approximate polytopes using sparse cuts under various settings. We propose a variant on feasibility pump that automatically detects and harnesses sparsity. We study the ratio of the number of integral extreme points to the total number of extreme points for a family of random polytopes as a function of sparsity. Finally, we discuss the strength of multi-row aggregation cuts in the context of sign-pattern integer programs.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectInteger programming
dc.subjectSparsity
dc.titleSparsity in integer programming
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentIndustrial and Systems Engineering
thesis.degree.levelDoctoral
dc.contributor.committeeMemberGoldsman, David
dc.contributor.committeeMemberMolinaro, Marco
dc.contributor.committeeMemberSun, Andy
dc.contributor.committeeMemberToriello, Alejandro
dc.date.updated2017-06-07T17:38:41Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record