Is there an easy formal proof for this: http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/special-case-of-integer-cuts.html? I think I derived it once. The more general cut is derived here: http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/integer-cuts.html.
Update. Here are my dabblings. First we go back to the derivation shown here and take the final formulation for the cut. From there we can do:
You are assuming that $y$ is binary, not just integer, correct? The constraint $\sum_i y_i = n$ and feasibility of $y^*$ imply that $\sum_{i|y^*_i = 1}y^*_i = n$, violating the cut.
ReplyDeleteNow suppose that $z$ is another solution excluded by the cut, and assume that $z$ is feasible in the original problem (so $\sum_i z_i = n$). It follows that $\sum_{i|y^*_i = 1}z_i = n = \sum_{i|y^*_i = 1}y^*_i$, and therefore $y^*_i = 1 \implies z_i = 1$. Since $z$ and $y^*$ both contain $n$ components equal to 1, in the same places, it must be that $y^*_i = 0 \implies z_i = 0$ and so $z = y^*$ (i.e., the cut excludes only the one solution it was designed to exclude).
Thanks very much. I also developed a more "don't think, just do the math" type of derivation.
ReplyDelete