I recently saw a question on a help forum that fits the following pattern. The context is an optimization model (mixed integer program). There is a continuous variable xx and a constant value aa (frequently but not always 0), and we want to distinguish among three cases (with different consequences in the model): x<a;x<a; x=a;x=a; or x>a.x>a. Each case has separate consequences within the model, which I will call C1,C1, C2C2 and C3C3 respectively. Variations on this question arise frequently. For instance, make xx the difference of two variables, set a=0a=0 and you are distinguishing whether the difference is negative, zero or positive.
To make things work properly, we need xx to be bounded, say L≤x≤U.L≤x≤U. The goal is to break the feasible range of xx into three intervals. To do so, we will introduce a trio of binary variables, y1,y2,y3y1,y2,y3 together with the constraint y1+y2+y3=1.y1+y2+y3=1. We will come up with constraints such that fixing y1=1y1=1 puts you in the left portion of the domain, fixing y2=1y2=1 puts you in the middle portion, and fixing y3=1y3=1 puts you in the right portion. The yy variables are then used elsewhere in the model to enforce whichever condition CC applies.
I'm using three variables for clarity. You can get by with two binary variables (changing the equality constraint above to ≤≤), where both variables equaling zero defines one of the domain intervals. Figure 1 shows what the user wants and how the yy variables relate to it.
![]() |
Figure 1 |
The intervals for xx are [L,a)[L,a) when y1=1y1=1, the singleton [a,a][a,a] when y2=1,y2=1, and (a,U](a,U] when y3=1.y3=1. Unfortunately, the user cannot have what the user wants because the feasible region of a MIP model must be closed, and the first and third intervals in Figure 1 are not closed. Closing them results in Figure 2.
![]() |
Figure 2 |
The intervals for xx are now [L,a],[L,a], [a,a][a,a] and [a,U].[a,U]. The good news is that this decomposition is easy to accomplish. The bad news is that the user likely will not accept it. If x=ax=a, any one of the yy variables could take the value 1, so any of the three conditions could be triggered.
This brings us to the first (and more common) of two possible compromises. We can change the strict inequality x>ax>a to the weak inequality x≥a+ϵx≥a+ϵ where ϵϵ is some small positive number, and do something analogous with the left interval. The result is Figure 3.
![]() |
Figure 3 |
Now y1=1⟹x≤a−ϵ,y1=1⟹x≤a−ϵ, y2=1⟹x=a,y2=1⟹x=a, and y3=1⟹x≥a+ϵ. The good news is that all three intervals are closed. The bad news is that values of x between a−ϵ and a or between a and a+ϵ are suddenly infeasible, whereas they were feasible in the original problem. Also note that any tiny deviation from a will throw x into no man's land. That leads to one more possibility, involving yet another positive constant δ<ϵ and shown in Figure 4.
![]() |
Figure 4 |
The algebra to put either Figure 3 or Figure 4 into force is actually pretty straightforward. You just need to write a pair of inequalities ⋯≤x≤… where the left side expression is the sum of each y variable times the lower bound that would apply when that variable is 1 and the right expression is the sum of each y variable times the upper bound that would apply. So for Figure 3, where the intervals are [L,a−ϵ], [a,a] and [a+ϵ,U], we would have Ly1+ay2+(a+ϵ)y3≤x≤(a−ϵ)y1+ay2+Uy3. For Figure 4, the constraints would be Ly1+(a−ϵ+δ)y2+(a+ϵ)y3≤x≤(a−ϵ)y1+(a+ϵ−δ)y2+Uy3.
There is one "tactical" point to consider. When this is first explained to someone who was unaware that strict inequalities are verboten, they are often tempted to set ϵ=10−G where G is the gross domestic product of their native country. The problem is that the solver is using finite precision computer arithmetic, and every solver has a tolerance value τ (small but not zero) such that coming within τ of satisfying a constraint is "close enough". If you pick ϵ (or δ) too small, it has the same consequence as setting it equal to 0 in terms of how valid the solutions are. You can end up with a value of a for x (to within rounding error) triggering consequence C1 or C3 rather than C2, or a value of x strictly greater than a triggering C2 (or possibly even C1), and so on. So ϵ (and, if needed, δ) must be greater than the rounding tolerance used by the solver.
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.