Generalized Cuts in Diophantine Programming

In the generation of an additional constraint or cut for integer programming introduced by Ralph Gomory, there is a certain parameter whose value is customarily chosen so that one of the original variables has a zero coefficient in the cut-equation. In this paper we consider alternative values of the parameter and refer to any linear combination of the original source equation and this cut as a “generalised cut”. Attention is then focused, as customary, on those cuts of this type for which the original variable has a zero coefficient. In particular, we show how to determine values for Gomory's parameter so that only a subset of the feasible solutions to the cuts used by Gomory's method of integer forms are feasible for the generalised cuts.

• 저널Management Science · 13(3) · 254–268
• 토픽Commutative Algebra and Its Applications · Algebra and Number Theory
• DOI10.1287/mnsc.13.3.254
• 저자Fred Glover