CUTTING PLANES FOR INTEGER PROGRAMS WITH GENERAL INTEGER VARIABLES

We investigate the use of cutting planes for integer programs with gen eral integer variables. We show how cutting planes arising from knapsa ck inequalities can be generated and lifted as in the case of 0-1 vari ables. We also explore the use of Gomory's mixed-integer cuts. We addr ess both theoretical and computational issues and show how to embed th ese cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of tes t problems arising from practical applications. (C) 1998 The Mathemati cal Programming Society, Inc. Published by Elsevier Science B.V.