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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/41133 |
| Date | 15 June 2011 |
| Creators | Chen, Kenneth |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0058 seconds