CglOddHole

Contributor and Maintainer: John J. Forrest (@jjhforrest)

Generates odd holes cuts. This looks at all rows of type sum x(i) <= 1 (or == 1) (with x binary) and sees if there is an odd cycle cut. See Grotschel, Lovasz and Schrijver (1988) for the method. This is then lifted by using the corresponding Chvatal cut i.e. by summing up all rows in the cycle. The right hand side will be odd and all odd coefficients can be reduced by one. The constraint is sum even(j)*x(j) <= odd which can be replaced by sum (even(j)/2)*x(j) <= (odd-1.0)/2. A similar cut can be generated for sum x(i) >= 1.

References:

• M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988. Sections 7.1 and 8.3.