 |
|
sponsored by
Title : Mingling: Mixed-Integer Rounding with Bounds
Date : Oct 1, 2007
Speaker : Alper Atamturk, Associate Professor
Affiliation : Industrial Engineering and Operations Research, University of California - Berkeley
Abstract
Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid cuts for mixed-integer programming. MIR cuts tend to work better for problems with unbounded integer variables. Computational experience suggests that for problems with 0-1 variables, cuts based on lifting techniques are more effective. This is not surprising because lifting techniques make explicit use of the bounds on the variables, whereas the MIR procedure does not.
In this talk, we will first review the superadditive lifting techniques for mixed-integer programming and the corresponding lifted inequalities. Then, we will describe a simple procedure, which we call mingling, for incorporating variable bound information into mixed-integer rounding. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets with bounded variables. We will show that facets of the mixed-integer knapsack sets derived earlier by superadditive lifting techniques are, indeed, mingling inequalities.
Joint work with Oktay Gunluk.
Biosketch
Alper Atamturk is an Associate Professor of Industrial Engineering and Operations Research at the University of California-Berkeley. His research interests include integer programming (combinatorial, conic, mixed-integer), robust optimization under uncertainty, and network design in the logistics of production, distribution, and telecommunication. He is currently on sabbatical leave from UC Berkeley and an Adjunct Professor in the School of Industrial and Systems Engineering at the Georgia Institute of Technology.
