Show simple item record

dc.contributor.authorTyber, Steven Jayen_US
dc.date.accessioned2013-06-15T02:41:00Z
dc.date.available2013-06-15T02:41:00Z
dc.date.issued2013-02-19en_US
dc.identifier.urihttp://hdl.handle.net/1853/47560
dc.description.abstractRecent developments in mixed integer programming have highlighted the need for multi-row cuts. To this day, the performance of such cuts has typically fallen short of the single-row Gomory mixed integer cut. This disparity between the theoretical need and the practical shortcomings of multi-row cuts motivates the study of both the mixed integer cut and multi-row cuts. In this thesis, we build on the theoretical foundations of the mixed integer cut and develop techniques to derive multi-row cuts. The first chapter introduces the mixed integer programming problem. In this chapter, we review the terminology and cover some basic results that find application throughout this thesis. Furthermore, we describe the practical solution of mixed integer programs, and in particular, we discuss the role of cutting planes and our contributions to this theory. In Chapter 2, we investigate the Gomory mixed integer cut from the perspective of group polyhedra. In this setting, the mixed integer cut appears as a facet of the master cyclic group polyhedron. Our chief contribution is a characterization of the adjacent facets and the extreme points of the mixed integer cut. This provides insight into the families of cuts that may work well in conjunction with the mixed integer cut. We further provide extensions of these results under mappings between group polyhedra. For the remainder of this thesis we explore a framework for deriving multi-row cuts. For this purpose, we favor the method of superadditive lifting. This technique is largely driven by our ability to construct superadditive under-approximations of a special value function known as the lifting function. We devote our effort to precisely this task. Chapter 3 reviews the theory behind superadditive lifting and returns to the classical problem of lifted flow cover inequalities. For this specific example, the lifting function we wish to approximate is quite complicated. We overcome this difficulty by adopting an indirect method for proving the validity of a superadditive approximation. Finally, we adapt the idea to high-dimensional lifting problems, where evaluating the exact lifting function often poses an immense challenge. Thus we open entirely unexplored problems to the powerful technique of lifting. Next, in Chapter 4, we consider the computational aspects of constructing strong superadditive approximations. Our primary contribution is a finite algorithm that constructs non-dominated superadditive approximations. This can be used to build superadditive approximations on-the-fly to strengthen cuts derived during computation. Alternately, it can be used offline to guide the search for strong superadditive approximations through numerical examples. We follow up in Chapter 5 by applying the ideas of Chapters 3 and 4 to high-dimensional lifting problems. By working out explicit examples, we are able to identify non-dominated superadditive approximations for high-dimensional lifting functions. These approximations strengthen existing families of cuts obtained from single-row relaxations. Lastly, we show via the stable set problem how the derivation of the lifting function and its superadditive approximation can be entirely embedded in the computation of cuts. Finally, we conclude by identifying future avenues of research that arise as natural extensions of the work in this thesis.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectInteger programmingen_US
dc.subjectSuperadditive liftingen_US
dc.subjectCorner polyhedraen_US
dc.subjectFinite group polyhedraen_US
dc.subjectFixed-charge flowen_US
dc.subjectKnapsacken_US
dc.subject.lcshInteger programming
dc.subject.lcshOperations research
dc.titleCutting planes in mixed integer programming: theory and algorithmsen_US
dc.typeDissertationen_US
dc.description.degreePhDen_US
dc.contributor.departmentIndustrial and Systems Engineeringen_US
dc.description.advisorCommittee Co-Chair: Ahmed, Shabbir; Committee Co-Chair: Nemhauser, George; Committee Member: Dey, Santanu; Committee Member: Gu, Zonghao; Committee Member: Vempala, Santoshen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record