Scaling-based Methods in Optimization and Cut Generation

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