Back to search

Georgia Institute of Technology

Sparsity in integer programming

Abstract

dc:description.abstract

Sparse 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.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Iroume, Andres
Advisor dc:contributor.advisor
  • Dey, Santanu S.
Committee members dc:contributor.committeemember
  • Goldsman, David
  • Molinaro, Marco
  • Sun, Andy
  • Toriello, Alejandro

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/58207

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Iroume, Andres. Sparsity in integer programming. Doctoral thesis, Georgia Institute of Technology, 2017. http://hdl.handle.net/1853/58207