Cutting-plane theory: Algebraic methods

AbstractThis paper is a survey, with new results, of the algebraic approach to cutting-planes. The new results are a subadditive dual program for integer programs, and a generalization of R. Gomory's linear inequality characterization of the cuts valid for the group problem. We also provide some results on the large family of alternate group problems, in addition to the one group problem that is conventionally thought of in connection with the algebraic approach. In terms of expository material, we shall provide very concise proofs of the most well-known results in the basic papers of the algebraic approach. (Note: This is a revision of Part I of MSRR no. 370)