Sequential pairing of mixed integer inequalities

被引:12
作者
Guan, Yongpei
Ahmed, Shabbir
Nemhauser, George L.
机构
[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA
[2] Univ Oklahoma, Sch Ind Engn, Norman, OK 73019 USA
基金
美国国家科学基金会;
关键词
integer programming; cutting planes;
D O I
10.1016/j.disopt.2006.10.003
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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. (c) 2007 Published by Fisevier B.V.
引用
收藏
页码:21 / 39
页数:19
相关论文
共 11 条
[1]  
Atamtürk A, 2000, MATH PROGRAM, V89, P35, DOI 10.1007/s101070000154
[2]   STRONG FORMULATIONS FOR MULTI-ITEM CAPACITATED LOT SIZING [J].
BARANY, I ;
VANROY, TJ ;
WOLSEY, LA .
MANAGEMENT SCIENCE, 1984, 30 (10) :1255-1261
[3]  
Birge J.R., 1997, INTRO STOCHASTIC PRO
[4]   CHVATAL CLOSURES FOR MIXED INTEGER PROGRAMMING-PROBLEMS [J].
COOK, W ;
KANNAN, R ;
SCHRIJVER, A .
MATHEMATICAL PROGRAMMING, 1990, 47 (02) :155-174
[5]  
GUAN Y, 2005, THESIS GEORGIA I TEC
[6]  
GUAN Y, 1923, P 11 INT C INT PROGR
[7]   A Branch-and-Cut algorithm for the stochastic uncapacitated lot-sizing problem [J].
Guan, YP ;
Ahmed, S ;
Nemhauser, GL ;
Miller, AJ .
MATHEMATICAL PROGRAMMING, 2006, 105 (01) :55-84
[8]   Mixing mixed-integer inequalities [J].
Günlük, O ;
Pochet, Y .
MATHEMATICAL PROGRAMMING, 2001, 90 (03) :429-457
[9]   Dynamic knapsack sets and capacitated lot-sizing [J].
Loparic, M ;
Marchand, H ;
Wolsey, LA .
MATHEMATICAL PROGRAMMING, 2003, 95 (01) :53-69
[10]  
Nemhauser G. L., 1988, INTEGER COMBINATORIA