Thursday, February 23, 2017

Another Absolute Value Question

Someone asked whether it is possible to eliminate the absolute value from the constraintLx|y|UxLx|y|Ux(where L0L0 and U>0U>0 are constants, xx is a binary variable, and yy is a continuous variable). The answer is yes, but what it takes depends on whether L=0L=0 or L>0L>0.

The easy case is when L=0L=0. There are two possibilities for the domain of yy: either y[0,0]y[0,0] (if x=0x=0) or y[U,U]y[U,U] (if x=1x=1). One binary variable is enough to capture two choices, so we don't need any new variables. We just need to rewrite the constraint asUxyUx.UxyUx.If L>0L>0, then there are three possibilities for the domain of yy: [U,L][0,0][L,U][U,L][0,0][L,U]. That means we'll need at least two binary variables to cover all choices. Rather than change the interpretation of xx (which may be used elsewhere in the questioner's model), I'll introduce two new binary variables (z1z1 for the left interval and z2z2 for the right interval) and link them to xx via x=z1+z2x=z1+z2. That leads to the following constraints:Uz1yLz1+U(1z1)Uz1yLz1+U(1z1)andLz2U(1z2)yUz2.Lz2U(1z2)yUz2. If x=0x=0, both z1z1 and z2z2 must be 0, and the new constraints force y=0y=0. If x=1x=1, then either z1=1z1=1 or z2=1z2=1 (but not both). Left to the reader as an exercise: verify that z1=1UyLz1=1UyL while z2=1LyUz2=1LyU.

No comments:

Post a Comment

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.