Show simple item record

dc.contributor.authorFukasawa, Ricardoen_US
dc.date.accessioned2008-09-17T19:28:15Z
dc.date.available2008-09-17T19:28:15Z
dc.date.issued2008-07-02en_US
dc.identifier.urihttp://hdl.handle.net/1853/24660
dc.description.abstractSingle-row mixed-integer programming (MIP) problems have been studied thoroughly under many different perspectives over the years. While not many practical applications can be modeled as a single-row MIP, their importance lies in the fact that they are simple, natural and very useful relaxations of generic MIPs. This thesis will focus on such MIPs and present theoretical and computational advances in their study. Chapter 1 presents an introduction to single-row MIPs, a historical overview of results and a motivation of why we will be studying them. It will also contain a brief review of the topics studied in this thesis as well as our contribution to them. In Chapter 2, we introduce a generalization of a very important structured single-row MIP: Gomory's master cyclic group polyhedron (MCGP). We will show a structural result for the generalization, characterizing all facet-defining inequalities for it. This structural result allows us to develop relationships with MCGP, extend it to the mixed-integer case and show how it can be used to generate new valid inequalities for MIPs. Chapter 3 presents research on an algorithmic view on how to maximally lift continuous and integer variables. Connections to tilting and fractional programming will also be presented. Even though lifting is not particular to single-row MIPs, we envision that the general use of the techniques presented should be on easily solvable MIP relaxations such as single-row MIPs. In fact, Chapter 4 uses the lifting algorithm presented. Chapter 4 presents an extension to the work of Goycoolea (2006) which attempts to evaluate the effectiveness of Mixed Integer Rounding (MIR) and Gomory mixed-integer (GMI) inequalities. By extending his work, natural benchmarks arise, against which any class of cuts derived from single-row MIPs can be compared. Finally, Chapter 5 is dedicated to dealing with an important computational problem when developing any computer code for solving MIPs, namely the problem of numerical accuracy. This problem arises due to the intrinsic arithmetic errors in computer floating-point arithmetic. We propose a simple approach to deal with this issue in the context of generating MIR/GMI inequalities.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectCutting planesen_US
dc.subjectMixed integer programmingen_US
dc.subjectMixed integer knapsacken_US
dc.subject.lcshInteger programming
dc.subject.lcshMathematical optimization
dc.subject.lcshKnapsack problem (Mathematics)
dc.titleSingle-row mixed-integer programs: theory and computationsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentIndustrial and Systems Engineeringen_US
dc.description.advisorCommittee Chair: William J. Cook; Committee Member: Ellis Johnson; Committee Member: George Nemhauser; Committee Member: Robin Thomas; Committee Member: Zonghao Guen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record