Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Iterated Chvatal-Gomory cuts and the geometry of numbers
AU - Aliev, Iskander
AU - Letchford, Adam
PY - 2014
Y1 - 2014
N2 - Chvatal-Gomory cutting planes (CG-cuts for short) are a fundamental tool in Integer Programming. Given any single CG-cut, one can derive an entire family of CG-cuts, by "iterating" its multiplier vector modulo one. This leads naturally to two questions: first, which iterates correspond to the strongest cuts, and, second, can we find such strong cuts efficiently? We answer the first question empirically, by showing that one specific approach for selecting the iterate tends to perform much better than several others. The approach essentially consists in solving a nonlinear optimization problem over a special lattice associated with the CG-cut. We then provide a partial answer to the second question, by presenting a polynomial-time algorithm that yields an iterate that is strong in a certain well-defined sense. The algorithm is based on results from the algorithmic geometry of numbers.
AB - Chvatal-Gomory cutting planes (CG-cuts for short) are a fundamental tool in Integer Programming. Given any single CG-cut, one can derive an entire family of CG-cuts, by "iterating" its multiplier vector modulo one. This leads naturally to two questions: first, which iterates correspond to the strongest cuts, and, second, can we find such strong cuts efficiently? We answer the first question empirically, by showing that one specific approach for selecting the iterate tends to perform much better than several others. The approach essentially consists in solving a nonlinear optimization problem over a special lattice associated with the CG-cut. We then provide a partial answer to the second question, by presenting a polynomial-time algorithm that yields an iterate that is strong in a certain well-defined sense. The algorithm is based on results from the algorithmic geometry of numbers.
KW - integer programming
KW - cutting planes
KW - geometry of numbers
U2 - 10.1137/130926389
DO - 10.1137/130926389
M3 - Journal article
VL - 24
SP - 1294
EP - 1312
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
SN - 1095-7189
IS - 3
ER -