Topics in group methods for integer programming

Lattice-free sets;T-space facets;Mixed-integer programming

Chen, Kenneth ; Mathematics

University:Georgia Institute of Technology

Department:Mathematics

关键词: Lattice-free sets;    T-space facets;    Mixed-integer programming;   

Others  :  https://smartech.gatech.edu/bitstream/1853/41133/1/chen_kenneth_201108_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

In 2003, Gomory and Johnson gave two different three-slope T-spacefacet constructions, both of which shared a slope with the correspondingGomory mixed-integer cut.We give a new three-slope facetwhich is independent of the GMIC and also give a four-slopeT-space facet construction, which to our knowledge, is the firstfour-slope construction.We describe an enumerative framework for the discovery of T-spacefacets.Using an algorithm by Harvey for computing integer hulls in theplane, 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 beused to derive facet-defining inequalities of the integer hull.We then present computational results using these derivations wherenon-basic integer variables are strengthened using Balas-Jeroslow lifting.