Topic
  • 6 replies
  • Latest Post - ‏2013-12-20T22:02:00Z by QiuFeng
QiuFeng
QiuFeng
4 Posts

Pinned topic discontinuous piece-wise linear function modeling

‏2013-12-19T15:59:27Z |

Hi guys, 

         I'm trying to model a discontinuous piece-wise linear function. But I couldn't figure out. Take an simple example, function f of t is two pieces: when t is in [a, b), f(t) =0; when t is in [b, c], f(t)=1.

 

         How can I use binary variable to model this function? Note that the first piece is open ended.  I know CPLEX concert has a function can do a similar job. But that is not what I want. I need an explicit linear formulation with binary variable. Any input is appreciated!
 
 
Happy holiday!
  • PaulRubin
    PaulRubin
    58 Posts

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-19T20:35:50Z  

     

    You might want to look at this blog post.

     

  • QiuFeng
    QiuFeng
    4 Posts

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-19T21:29:15Z  
    • PaulRubin
    • ‏2013-12-19T20:35:50Z

     

    You might want to look at this blog post.

     

    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. 

  • PaulRubin
    PaulRubin
    58 Posts

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-20T02:21:08Z  
    • 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

  • QiuFeng
    QiuFeng
    4 Posts

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-20T17:45:38Z  
    • 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? 

  • PaulRubin
    PaulRubin
    58 Posts

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-20T20:23:14Z  
    • 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.

  • QiuFeng
    QiuFeng
    4 Posts

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-20T22:02:00Z  
    • 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 !