ACO Home Page   Admission Information Program Description Affiliated Faculty Students Alumni Research Program ACO News ACO Events ACO Internal   Georgia Tech College of Computing School of Ind. Sys. Eng. School of Mathematics School of Electrical Eng.   Help Advanced Search   Contact WEBmaster

Ricardo Fukasawa

Title: Single-row Mixed-integer Programs: Theory and Computations

Time:	Wednesday, June 25th, 2:00pm
Location:	Groseclose 226A
Advisor:	Dr. William Cook
Committee:	Dr. Robin Thomas, School of Mathematics
	Dr. George Nemhauser, School of Industrial Systems and Engineering
	Dr. Ellis Johnson, School of Industrial Systems and Engineering
	Dr. Zonghao Gu, School of Industrial Systems and Engineering
Reader:	Dr. Oktay Gunluk, IBM Research

Abstract:

Single-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 a brief introduction, as well as a summary of the contributions of the thesis.

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.

<Plain-Text Page>  (ACO Program Web Pages)

. . . . . . . . . . . . . .

This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: May 23, 2008 Georgia Tech Disclaimer: Notwithstanding any language to the contrary, nothing contained herein constitutes nor is intended to constitute an offer, inducement, promise, or contract of any kind. The data contained herein is for informational purposes only and is not represented to be error free. Any links to non-Georgia Tech information are provided as a courtesy. They are not intended to nor do they constitute an endorsement by the Georgia Institute of Technology of the linked materials.