Technical Note—Strengthened Dantzig Cuts for Integer Programming

1 February 1972

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 20 (1) , 178-182
https://doi.org/10.1287/opre.20.1.178

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.

Keywords

STRENGTHENED
INTEGER PROGRAMMING
DANTZIG CUTS
GROUP THEORETIC
FINITE PROCEDURE
DANTZIG PROPOSED
HOFFMAN SHOWED

This publication has 0 references indexed in Scilit: