NOTICE: SMARTech content freeze Dec. 10 - 17. The Library will be unable to deposit or edit content during this scheduled maintenance

Show simple item record

dc.contributor.authorGoycoolea, Marcos G.en_US
dc.date.accessioned2007-03-27T18:03:17Z
dc.date.available2007-03-27T18:03:17Z
dc.date.issued2006-11-13en_US
dc.identifier.urihttp://hdl.handle.net/1853/13956
dc.description.abstractIn this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general MIPs. In the first study I introduce a new class of cutting planes which I call the Generalized Domino Parity (GDP) inequalities. My main achievements with regard to these are: (1) I show that these are valid for the TSP and for the graphical TSP. (2) I show that they generalize most well-known TSP inequalities (including combs, domino-parity constraints, clique-trees, bipartitions, paths and stars). (3) I show that a sub-class of these (which contains all clique-tree inequalities w/ a fixed number of handles) can be separated in polynomial time, on planar graphs. My second study can be subdivided in two parts. In the first of these I study the Mixed Integer Knapsack Problem (MIKP) and develop a branch-and-bound based algorithm for solving it. The novelty of the approach is that it exploits the notion of "dominance" in order to effectively prune solutions in the branch-and-bound tree. In the second part, I develop a Mixed Integer Rounding (MIR) cut separation heuristic, and embed the MIKP solver in a column generation algorithm in order to assess the performance of said heuristic. The goal of this study is to understand why no other class of inequalities derived from single-row systems has been able to outperform the MIR. Computational results are presented.en_US
dc.format.extent1425451 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectTraveling salesman problemen_US
dc.subjectCutting planesen_US
dc.subjectMixed integer roundingen_US
dc.subjectMixed integer programmingen_US
dc.titleCutting Planes for Large Mixed Integer Programming Modelsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentIndustrial and Systems Engineeringen_US
dc.description.advisorCommittee Chair: Cook, William; Committee Member: Gu, Zonghao; Committee Member: Johnson, Ellis; Committee Member: Nemhauser, George; Committee Member: Thomas, Robinen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record