Return to search

Topics in group methods for integer programming

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.

Identiferoai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/41133
Date15 June 2011
CreatorsChen, Kenneth
PublisherGeorgia Institute of Technology
Source SetsGeorgia Tech Electronic Thesis and Dissertation Archive
Detected LanguageEnglish
TypeDissertation

Page generated in 0.0017 seconds