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 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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/24660 |
| Date | 02 July 2008 |
| Creators | Fukasawa, Ricardo |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.0026 seconds