Article ID: | iaor20073110 |
Country: | Netherlands |
Volume: | 4 |
Issue: | 1 |
Start Page Number: | 21 |
End Page Number: | 39 |
Publication Date: | Mar 2007 |
Journal: | Discrete Optimization |
Authors: | Nemhauser George L., Ahmed Shabbir, Guan Yongpei |
We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts.