インダストリアルエンジニアリングとマネジメント

Sequential Lifting of General Integer Variables for Integer Programs

Abstract

Todd Easton and Talia Gutierrez

Lifting integer variables is a widely used technique to create strong cutting planes. In 1975, Wolsey introduced a method to compute the exact sequential lifting coefficients of bounded integer variables by solving many integer programs. This paper presents a new technique to perform exact sequentially up and down lifting of general integer variables. The technique requires solving only a single branching tree. Some computational results demonstrate that this new sequential lifting technique performed approximately 11 times faster than Wolsey?s technique.