|Version 4 (modified by guest, 8 years ago) (diff)|
Contributor: John J. Forrest
Maintainer: John J. Forrest, jjforre@…
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.
Documentation and Bug Reports
See the sections "Doxygen Documentation" and "Project Links" on the Cgl main page