Thursday, October 20, 2011

Special case of integer cuts

In http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/integer-cuts.html we derive a constraint that forbids an integer configuration y*.

If the model contains a constraint like:

image

then we can simplify the integer cut to:

image

 

as we only need to keep track of the variables flipping from 1 → 0. This is because any variable moving from 0 → 1 will cause another variable to move from 1 → 0.

This simpler constraint has fewer nonzeroes which is important if we add a lot of such cuts, as is the case in one of my models.