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

    Scaling-based methods in optimization and cut generation

    Thumbnail
    View/Open
    PAVELKA-DISSERTATION-2017.pdf (729.1Kb)
    Date
    2017-03-30
    Author
    Pavelka, Jeffrey William
    Metadata
    Show full item record
    Abstract
    This thesis addresses both theoretical and practical concerns in integer programming. In Chapter 2 we discuss scaling-based primal methods for integer programming. Such methods optimize by repeatedly solving augmentation problems - given a polytope, cost vector, and feasible solution, either return a solution with improved objective value or assert that none exists. It is known that with clever scaling of the objective vector, one can optimize by solving only polynomially many augmentation sub-problems. We discuss two known scaling algorithms - bit scaling and geometric scaling - and prove tightened bounds on the number of augmentations necessary. We also explore the practical feasibility of such schemes with a computational study. Chapter 3 addresses questions regarding Chvatal-Gomory (CG) cuts for 0/1 polytopes. The CG rank of such polytopes is known to be $O(n^2\log(n))$ in general. We prove a tighter bound for such polyhedra which, while still $O(n^2\log(n))$ in general, implies asymptotically improved bounds for several classes of polyhedra. Furthermore, we address the question of complexity for the separation problem over a family of cuts related to CG cuts, called mod-k cuts. We show this problem to be NP complete. Finally, Chapter 4 turns away from integer programming theory, instead focusing on an application in inventory management. We study a scenario (inspired by collaboration with a large online retailer) in which replenishment opportunities arise according to a process outside our control. We devise a stochastic model for use in this scenario, and test its usefulness by way of a simulation study using actual sales data from our collaborator. Of particular interest here is the use of data-driven prediction techniques to tune model parameters. We demonstrate that predictions culled from sophisticated machine learning techniques (e.g.\ neural network regression) can provide a boost in performance as compared to simpler, classical techniques (e.g.\ moving averages).
    URI
    http://hdl.handle.net/1853/58250
    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