• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Sparsity in integer programming

    Thumbnail
    View/Open
    IROUME-DISSERTATION-2017.pdf (401.2Kb)
    Date
    2017-01-11
    Author
    Iroume, Andres
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/58207
    Collections
    • Georgia Tech Theses and Dissertations [23877]
    • School of Industrial and Systems Engineering Theses and Dissertations [1457]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology