wiki:CglOddHole

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.


Papers, Presentations, and References

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

Documentation and Bug Reports

See the section "Project Links" on the Cgl main Trac page.

Last modified 12 years ago Last modified on Nov 18, 2006 12:24:57 PM