Tuesday, June 2, 2009

GAMS: Piecewise linear functions with SOS2 variables

Sometimes we need to represent a piecewise linear function, like:

sos2-1

This can be modeled with the following:

sos2-2

Equation (1) is called the “reference row”, equation (2) the “function row” and equation (3) the “convexity row”. Many MIP solvers have so-called SOS2 facilities: special ordered sets of type 2. The lambda variables form a SOS2 set, so this makes using this very simple (it is possibly to simulate this with extra binary variables). In GAMS this looks like:

variables y,x;
sos2 variables lambda(k);

equations refrow, funrow, convexity;

refrow.. x =e= sum(k, lambda(k)*xbar(k));
funrow.. y =e= sum(k, lambda(k)*ybar(k));
convexity.. sum(k, lambda(k)) =e= 1;

Notes:

  • It is important to keep the “set-index” last. See the fragment of a model I am working at now:

defq(i,t).. q(i,t) =e= sum(ic(i,c), lambda(i,t,c)*xpoints(c));

defcost(i,t)..  cost(i,t) =e= sum(ic(i,c), lambda(i,t,c)*ypoints(i,c));

convex(i,t)..  sum(ic(i,c),lambda(i,t,c)) =e= 1;

Here we need to keep c last in variable lambda. This makes sure we have i × t sets with c members. In this case c is dependent on i through the set ic(i,c).

  • AMPL has special language constructs to make this even easier.
  • MS Solver Foundation also has added SOS2 support.
  • GAMS has no facility to specify the reference weights (they are usually automatically generated to be 1,2,…).  Of course in many cases I can not make a good use of reference weights anyway, as I would not know any better values.

14 comments:

  1. hi Erwin,

    I am not sure if this is the correct place to post my question.

    i have an MINLP model involving sign function and absolute value functions. Is that possible to linearise them?

    also, this model is huge since I have data D(i,j) with 8000000 rows and 20 columns. the size of variables are similiar. Could you plase give me some hints on how GAMS can deals with that if i dont have enough memory (3.6G).

    If I solve it in GA as an MINLP, any tricks on how to avoid the premature situation ?

    Thanks alot.

    ReplyDelete
  2. They can be linearized using binary variables. Sometimes even convexity can be exploited. Also in some cases a smooth approximation can help. Anyway: better advice is only possible after looking at and studying the whole model.

    With GA make sure you can go worse with some probability, to allow escaping local optima.

    ReplyDelete
  3. Thanks a lot for your reply.

    Actually, the sign constraint is:

    X(i)=sign(X(i-1)-Y(i))

    X and Y only have the values of 0,1,-1

    looking forward......

    ReplyDelete
  4. I suspect this could be modeled using a "table lookup" using binary variables. Something like:

    sum(j, d(i,j))=1
    x(i-1)-y(i) = sum(j, p(j)*d(i,j))
    x(i) = sum(j, q(j)*d(i,j))
    p = [-2,-1,0,1,2]
    q = [-1,-1,0,1,1]

    ReplyDelete
  5. Hi Erwin,

    Can you explain what algorithm common MIP solvers use to solve SOS2 constraints? In particular, Coin-OR's Cbc?

    Thanks!

    ReplyDelete
  6. See the references in http://en.wikipedia.org/wiki/Special_ordered_set

    ReplyDelete
  7. Dear Erwin,
    I am a research scholar .i have recently started working in optimization area. Initially i want to represent any non linear function or curve with the help of piecewise linear approximation (interpolation as you have shown above) using Linear programming concept. I will be happy if you answer my following doubts
    1) In some book i found that Piecewise linear approximation (PLA) is used to find the optimal of non linear function. What is the use of PLA in LP?
    2) Can i simply use PLA concept to represent my non linear curve with line segments of pieces of line and not to get its optimal.Means my input to the LP program is non linear curve and output is optimal of it as well as its piecewise approximated curve?
    3) The above code of GAMS for piecewise linear interpolation is full or incomplete?Could you send me complete PLA code so i can have some hands on with PLI(piecewise linear interpolation)?My mail ID is dips164@gmail.com.

    ReplyDelete
  8. This comment has been removed by a blog administrator.

    ReplyDelete
  9. Hi Erwin,
    Would you please suggest me how to use SOS2 or how to do piece wise linear approximation for logarithmic function like log10(t^2 + 1) for a linear programming problem formulation.regards

    ReplyDelete
  10. Unless there is something to exploit, in general this can not be solved as an LP.

    ReplyDelete
  11. Hello Erwin,

    thanks for your contributions! I've used multiple of your webpages with great delight already. A question: how can you specify piecewise linear functions in multiple variables in GAMS?

    ReplyDelete
    Replies
    1. 1) Try to make it separable. E.g. z=x*y can be written as log(z) = log(x)+log(y). Now apply standard sos2 tricks.
      2) http://yetanothermathprogrammingconsultant.blogspot.com/2013/08/2d-interpolation-with-sos2-variables.html

      Delete
  12. This comment has been removed by the author.

    ReplyDelete
  13. Hi Erwin,
    Thanks for your useful blog

    I have always an unanswered question regarding SOS vars: How about the computational burden?
    As you know, if we model a piecewise-linear function by binary variables (big M method), it will result in increasing computational complexity and thus the more amount of time needed to solve the problem. I want to ask do SOS2 variables have the same effect on the computational complexity or they result in lighter models

    Thank you in advance,
    Hamid

    ReplyDelete