Back to search

Georgia Institute of Technology

Topics in linear and nonlinear discrete optimization

Abstract

dc:description.abstract

This work contributes to modeling, theoretical, and practical aspects of structured Mathematical Programming problems. Many real-world applications have nonlinear characteristics and can be modeled as Mixed Integer Nonlinear Programming problems (MINLP). Modern global solvers have significant difficulty handling large-scale instances of them. Several convexification and underestimation techniques were proposed in the last decade as a part of the solution process, and we join this trend. The thesis has three major parts. The first part considers MINLP problems containing convex (in the sense of continuous relaxations) and posynomial terms (also called monomials), i.e. products of variables with some powers. Recently, a linear Mixed Integer Programming (MIP) approach was introduced for minimization the number of variables and transformations for convexification and underestimation of these structured problems. We provide polyhedral analysis together with separation for solving our variant of this minimization subproblem, containing binary and bounded continuous variables. Our novel mixed hyperedge method allows to outperform modern commercial MIP software, providing new families of facet-defining inequalities. As a byproduct, we introduce a new research area called mixed conflict hypergraphs. It merges mixed conflict graphs and 0-1 conflict hypergraphs. The second part applies our mixed hyperedge method to a linear subproblem of the same purpose for another class of structured MINLP problems. They contain signomial terms, i.e. posynomial terms of both positive and negative signs. We obtain new facet-defining inequalities in addition to those families from the first part. The final part is dedicated to managing guest flow in Georgia Aquarium after the Dolphin Tales opening with applying a large-scale MINLP. We consider arrival and departure processes related to scheduled shows and develop three stochastic models for them. If demand for the shows is high, all processes become interconnected and require a generalized model. We provide and solve a Signomial Programming problem with mixed variables for minimization resources to prevent and control congestions.

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
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shapoval, Andriy
Advisor dc:contributor.advisor
  • Lee, Eva K.
Committee members dc:contributor.committeemember
  • Johnson, Ellis
  • Pokutta, Sebastian
  • Goldsman, David M.
  • Wu, D. J.

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Shapoval, Andriy. Topics in linear and nonlinear discrete optimization. Doctoral thesis, Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/53460