Abstract
dc:description.abstractIn 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 × 4Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/41133