*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Scaling-based Methods in Optimization and Cut Generation
Advisor: Dr. Sebastian Pokutta
Committee Members:
Dr. Chelsea White
Dr. Alejandro Toriello
Dr. Santanu Dey
Dr. Marc Pfetsch (TU Darmstadt)
Date and time: Thursday, February 16th, 10:00 AM.
Location: ISyE Main Building, room 341.
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).
