Sunday, October 2, 2011

Integer cuts

I received a few questions about how to form constraints that exclude a known 0-1 integer solution. Assume our solution we want to exclude is called y* then we can write:

image

This can be linearized as follows:

image

The final result is also sometimes written as the following constraint:

image

Note that y is a binary decision variable.

3 comments:

  1. I came across this on StackOverflow. Could you explain why you compare 2*soln - 1 to sum(soln) - 1
    WOuldn't sum(soln) give an integer rather than an array?

    ReplyDelete
  2. Hi Abdullah, the Stackoverflow topic adds one final step to this article. The article ends with two sums, one of which applies when y_i_star =1 and the other one when y_i_star=0. When you consider a single y_i_star item, if your item is in the first case, the left hand side is equal to (+ y_i), in the other case, the left hand side is (- y_i).
    You get exactly the same left hand side with sum "2*soln - 1", or more precisely with [sum((2 * y_i_star -1) * y_i) across all y_i_star]
    The right hand side is the same between the article's final step and stackoverflow's "sum(soln) - 1"

    ReplyDelete
    Replies
    1. ... hence we are indeed comparing integers on both sides (sorry for dodging the question)

      Delete