A family of valid inequalities for a general integer linear programming problem may be derived on the basis of the following simple algebraic considerations.
Let P be a polyhedron defined by a system of constraints written in standard form, that is to say having the expression Ax = b, x non negative and assume that the matrix A has m rows.
For each vector u with m components we may consider the linear combination of the rows of the system Ax = b with coefficients given by the components of u. In so doing we obtain the equality 1) which is trivially satisfied by any element in P. Let's take a new step and round off all the coefficients of the left hand side of equality 1). After this operation, each coefficient of the left hand side is not increased.
So, since by hypothesis the elements of P have non negative components, inequality 2) is satisfied by each element in P.
Moreover,note that each coefficient of the left hand side of inequality two is integer and thus, if we evaluate it in an integer vector x we obtain an integer number. This implies that, if we perform a new step and round off also the right hand side of inequality 2), we obtain a new inequality, the number 3, that is surely satisfied by each integer vector in P and thus by each element in P(S). In general, inequality 3) may be violated by fractional elements of P.
An inequality obtained in this way is called a Chvátal Inequality.
Evidently, we may construct an inequality of this type for each element u in Rm.