Back to search

Georgia Institute of Technology

Topics in group methods for integer programming

Abstract

dc:description.abstract

In 2003, Gomory and Johnson gave two different three-slope T-space facet constructions, both of which shared a slope with the corresponding Gomory mixed-integer cut. We give a new three-slope facet which is independent of the GMIC and also give a four-slope T-space facet construction, which to our knowledge, is the first four-slope construction. We describe an enumerative framework for the discovery of T-space facets. Using an algorithm by Harvey for computing integer hulls in the plane, we give a heuristic for quickly computing lattice-free triangles. Given two rows of the tableau, we derive how to exactly calculate lattice-free triangles and quadrilaterals in the plane which can be used to derive facet-defining inequalities of the integer hull. We then present computational results using these derivations where non-basic integer variables are strengthened using Balas-Jeroslow lifting.

Degree

thesis:*
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Kenneth
Advisor dc:contributor.advisor
  • Cook, William J.
Committee members dc:contributor.committeemember
  • Johnson, Ellis L.
  • Nemhauser, George L.
  • Parker, R. Gary
  • Tetali, Prasad

Subjects

dc:subject × 4

Identifiers

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

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

Chen, Kenneth. Topics in group methods for integer programming. Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41133