Sequential pairing of mixed integer inequalities |
| |
Authors: | Yongpei Guan Shabbir Ahmed George L. Nemhauser |
| |
Affiliation: | aSchool of Industrial Engineering, University of Oklahoma, 202 West Boyd, Norman, OK 73019, United States;bSchool of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA 30332, United States |
| |
Abstract: | 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. |
| |
Keywords: | Integer programming Cutting planes |
本文献已被 ScienceDirect 等数据库收录! |
|