Hi guys,
Hi guys,
- PaulRubin
- 2013-12-19T20:35:50Z
Hi Paul, That's a nice post. However, I'm not sure how the model is going to choose a function value at the breaking points. In the example above, I need f(b) = 1.
- QiuFeng
- 2013-12-19T21:29:15Z
Hi Paul, That's a nice post. However, I'm not sure how the model is going to choose a function value at the breaking points. In the example above, I need f(b) = 1.
You are bumping into a limitation of mathematical programming. Fundamentally, math programming algorithms rely on feasible regions being closed (and, typically, convex). The use of binary variables allows us to decompose the feasible region into subregions, in this case a <= t <= b and b <= t <= c. They still have to be closed, though. So when t = b, both f(t) = 0 and f(t) = 1 will be feasible, and the algorithm will choose whichever one leads to a better objective value.
One partial work-around is to split the domain into [a, b-epsilon] and [b, c], where epsilon is small and positive. The good news is that there will be no ambiguity around f(b). The bad news is that if the optimal solution has b-epsilon < t < b, you may end up with a suboptimal solution (although possibly only slightly suboptimal).
Paul
- PaulRubin
- 2013-12-20T02:21:08Z
You are bumping into a limitation of mathematical programming. Fundamentally, math programming algorithms rely on feasible regions being closed (and, typically, convex). The use of binary variables allows us to decompose the feasible region into subregions, in this case a <= t <= b and b <= t <= c. They still have to be closed, though. So when t = b, both f(t) = 0 and f(t) = 1 will be feasible, and the algorithm will choose whichever one leads to a better objective value.
One partial work-around is to split the domain into [a, b-epsilon] and [b, c], where epsilon is small and positive. The good news is that there will be no ambiguity around f(b). The bad news is that if the optimal solution has b-epsilon < t < b, you may end up with a suboptimal solution (although possibly only slightly suboptimal).
Paul
Hi Paul, Thanks for your explanation. Certainly open sets will not give an attainable optimal solution for a LP. But I was thinking, if we can model the following logic, then wen can get around it: if t=b, then f(t)=1. This is not "open set" thing. So whenever it comes to this breaking point, b, this constraint will choose the second segment.
but I know we can not model this, otherwise, we can have open sets in LP. Am I Right?
- QiuFeng
- 2013-12-20T17:45:38Z
Hi Paul, Thanks for your explanation. Certainly open sets will not give an attainable optimal solution for a LP. But I was thinking, if we can model the following logic, then wen can get around it: if t=b, then f(t)=1. This is not "open set" thing. So whenever it comes to this breaking point, b, this constraint will choose the second segment.
but I know we can not model this, otherwise, we can have open sets in LP. Am I Right?
You are correct that we cannot model it in a MILP. The problem is that f(t) = 0 for all t in [a, b) but not for all t in [a, b]. So the set where f = 0 is semi-open, not closed.
- PaulRubin
- 2013-12-20T20:23:14Z
You are correct that we cannot model it in a MILP. The problem is that f(t) = 0 for all t in [a, b) but not for all t in [a, b]. So the set where f = 0 is semi-open, not closed.
Thank you Paul! Happy Holidays !