Back to search

Georgia Institute of Technology

Scaling-based methods in optimization and cut generation

Abstract

dc:description.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(n2\log(n)) in general. We prove a tighter bound for such polyhedra which, while still O(n2\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).

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
  • Pavelka, Jeffrey William
Advisors dc:contributor.advisor
  • Pokutta, Sebastian
  • White, Chelsea C., III
Committee members dc:contributor.committeemember
  • Toriello, Alejandro
  • Dey, Santanu
  • Pfetsch, Marc

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Pavelka, Jeffrey William. Scaling-based methods in optimization and cut generation. Doctoral thesis, Georgia Institute of Technology, 2017. http://hdl.handle.net/1853/58250