Single-row mixed-integer programs: theory and computations

Cutting planes;Mixed integer programming;Mixed integer knapsack

Fukasawa, Ricardo ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Cutting planes;    Mixed integer programming;    Mixed integer knapsack;   

Others  :  https://smartech.gatech.edu/bitstream/1853/24660/1/fukasawa_ricardo_200808_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Single-row mixed-integer programming (MIP) problems have been studied thoroughlyunder many different perspectives over the years. While not many practicalapplications can be modeled as a single-row MIP, their importance lies in thefact that they are simple, natural and very useful relaxations of generic MIPs.This thesis will focus on such MIPs and present theoretical and computationaladvances in their study.Chapter 1 presents an introduction to single-row MIPs, a historical overviewof results and a motivation of whywe will be studying them. It will also contain a brief review of the topics studied in this thesisas well as our contribution to them.In Chapter 2, we introduce a generalization of a veryimportant structured single-row MIP: Gomory's master cyclic grouppolyhedron (MCGP). We will show a structural result for thegeneralization, 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 howit can be used to generate new valid inequalities for MIPs.Chapter 3 presents research on an algorithmic view on how to maximally liftcontinuous and integer variables. Connections to tilting and fractionalprogramming will also be presented. Even though lifting is not particular tosingle-row MIPs, we envision that the general use of the techniques presentedshould 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 cutsderived from single-row MIPs can be compared.Finally, Chapter 5 is dedicated to dealing with an important computational problem whendeveloping 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 asimple approach to deal with this issue in the context of generating MIR/GMI inequalities.