Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
6 replies Latest Post - ‏2013-12-20T22:02:00Z by QiuFeng
QiuFeng
QiuFeng
4 Posts
ACCEPTED ANSWER

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
    48 Posts
    ACCEPTED ANSWER

    Re: discontinuous piece-wise linear function modeling

    ‏2013-12-19T20:35:50Z  in response to QiuFeng

     

    You might want to look at this blog post.

     

    • QiuFeng
      QiuFeng
      4 Posts
      ACCEPTED ANSWER

      Re: discontinuous piece-wise linear function modeling

      ‏2013-12-19T21:29:15Z  in response to PaulRubin

      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
        48 Posts
        ACCEPTED ANSWER

        Re: discontinuous piece-wise linear function modeling

        ‏2013-12-20T02:21:08Z  in response to QiuFeng

        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
          ACCEPTED ANSWER

          Re: discontinuous piece-wise linear function modeling

          ‏2013-12-20T17:45:38Z  in response to PaulRubin

          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
            48 Posts
            ACCEPTED ANSWER

            Re: discontinuous piece-wise linear function modeling

            ‏2013-12-20T20:23:14Z  in response to QiuFeng

            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
              ACCEPTED ANSWER

              Re: discontinuous piece-wise linear function modeling

              ‏2013-12-20T22:02:00Z  in response to PaulRubin

              Thank you Paul!  Happy Holidays !