wiki:CglOddHole

Version 3 (modified by guest, 13 years ago) (diff)

--

CglOddHole

Contributor: John J. Forrest
Maintainer: John J. Forrest, jjforre@…

Introduction

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 "Project Links" Section on the Cgl main page