Originally posted by: QiuFeng

Hi guys, 

You might want to look at this blog post.

Originally posted by: QiuFeng

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

Originally posted by: QiuFeng

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.

Originally posted by: QiuFeng

Thank you Paul!  Happy Holidays !