Zero-half cuts

Defines zero-half cuts and offers an example.

Zero-half cuts are based on the observation that when the lefthand side of an inequality consists of integral variables and integral coefficients, then the righthand side can be rounded down to produce a zero-half cut. Zero-half cuts are also known as 0-1/2 cuts. To understand how zero-half cuts are generated, consider these two constraints over five integer variables with integer coefficients:

 x1 + 2x2 +  x3 + 3x4        <= 8 
 x1 +       3x3 +  x4 + 2x5  <= 5 

Now consider the sum of those two constraints:

 2x1 + 2x2 + 4x3 + 4x4 + 2x5 <= 13 

Divide that constraint by 2:

 x1 + x2 + 2x3 + 2x4 + x5 <= 6.5 

Round down the righthand side to get the zero-half cut:

 x1 + x2 + 2x3 + 2x4 + x5 <= 6