VALID INEQUALITIES AND SUBADDITIVITY FOR INTEGER PROGRAMMING PROBLEMS VALID INEQUALITIES AND SUBADDITIVITY FOR INTEGER PROGRAMMING PROBLEMS

minimize c(x subject to Ax = b 0 ^ x e Zn where A e Rmxn, b e Rn and c e R". Throughout this paper, R and Z denote the set of all real numbers and the set of all integers respec-tively. Suppose that the set X'={xeRn;Ax=b,0^xeZn) of feasible solutions is bounded and not empty. Let it be in Rn and no be a real number. An inequality nlx ^ 7To is called a valid inequality for X1 if it is satisfied by all x e X1. We consider the associated linear programming problem (Po) minimize c*x subject to Ax = b 0 ^ xe Rn. Let x ° be an optimal solution to the problem (Po). A valid inequality for X', n'x ^7ro, is called a cut if ^x0 < no