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:
This can be linearized as follows:
The final result is also sometimes written as the following constraint:
Note that y is a binary decision variable.
I came across this on StackOverflow. Could you explain why you compare 2*soln - 1 to sum(soln) - 1
ReplyDeleteWOuldn't sum(soln) give an integer rather than an array?
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).
ReplyDeleteYou 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"
... hence we are indeed comparing integers on both sides (sorry for dodging the question)
Delete