Technical Note—Strengthened Dantzig Cuts for Integer Programming

Abstract

In 1959, Dantzig proposed a particularly simple cut for integer programming. However, in 1963, Gomory and Hoffman showed that, in general, this cut does not provide a finite algorithm. In 1968, Bowman and Nemhauser showed that a slightly modified version of the Dantzig cut does provide a finite procedure. We show how this latter cut can be strengthened through the use of group-theoretic techniques.