multiple binary variables in mip

[Archiver]

been a long time after this question, but for future references:

first look at this:
http://yetanothermathprogrammingconsult ... -with.html

then, read here and find the appropriate code:
https://support.gams.com/gams:linearize ... r_function

cheers,
Amir

On Wednesday, March 28, 2012 at 3:15:13 AM UTC-5, Destin Zed wrote:

Dear Michael,

You are right. We are trying to model piecewise linear functions. I heard about SOS1 and SOS2 variables once in a presentation but did not care much at that time. But now it seems it is worth considering them. So, can you please elaborate what these variables are all about? How do formulations with SOS2 variables improve computational/solution efficiency? I tried to google and learn something about that but did not get much information.
Any good material you may need to recommend us to read about?

Best wishes,
Destin


On Mon, Mar 26, 2012 at 8:48 PM, Michael Ferris wrote:

It seems to me that you are modeling piecewise linear functions. There are a number of formulations of this which involve sos2 (or multiple sos1 variables) that seem to be quite efficient. There is also a large literature on this.

Michael Ferris

On Mar 26, 2012, at 10:02 AM, chen li wrote:

> Dear Destin,
> Thank you for your advice, it sounds like a great idea, I'll have a try and keep you posted.
>
> Thanks again~~
> Best,
> Chen
>
> 2012/3/26 Destin Zed
> Hi Chen,
>
> It is right. You have non-linearity in the formulations. You can probably solve it using mixed integer non-linear programming or DNLP or something similar not MIP. But that is what you probably don't like to do.
> Here is a MIP formulation of your problem:
> y - (a1x + b1) y - (a1x + b1)>=-M(1-s1);
> y - (a2x + b2) y - (a2x + b2)>=-M(1-s2);
> y - (a3x + b3) y - (a3x + b3)>=-M(1-(1-s1-s2));
> s1+s2 x x>=100*s2 + 200*(1-s1-s2);"
>
> Don't forget to set big-M value to the maximum possible value of y to avoid numerical difficulties.
>
> Hope this helps.
> Destin
>
>
> On Sun, Mar 25, 2012 at 8:27 AM, chen li wrote:
> Dear Muhajir and Destin ,
>
> Sorry for my late replying and thanks for both of your suggestions, these are really good ideas. I tried to solve the your suggestions like using "y = s1(a1x + b1) + s2(a2x + b2) + s3(a3x + b3) " and then define the constraints by using "s1+s2
> x x>=100*s2+200*(1-s1-s2);"
> However, gams told me "Endogenous operands for * not allowed in linear models". I think that's because I use Cplex to solve my MIP and x and s are both unknown variables for gams, so gams could not solve the equations like"x*s". But what else could I do if I only want to use MIP to solve this multi-binary problem?
>
>
> I appreciate your help~~
> Best,
> Chen
>
>
> 2012/3/22 Muhajir
> Hi again,
>
> In order to choose which y to be enforced for which x value, you may use your objective function. If for example your objective function is maximization and the coefficients ai and bi are positive, you may use
>
> max Obj1 + y
>
> Y=k1 +k2+k3;
> k1 k1 k2 k2 K3 k3
> where M is large positive number and Obj1 is your original objective
>
> Of course it depends on the Obj1 and the sign of the coefficients!
>
> hope this helps!
>
>
>
> On Thu, Mar 22, 2012 at 11:13 AM, Muhajir wrote:
> Hello Helena and Destin,
>
> How about this formulation:
>
> binary variables s1, s2
> s1+s2 x x>=100*s2+200*(1-s1-s2);
> Where M is a very large number
>
> Let me know if it works!
>
> regards,
>
>
> On Thu, Mar 22, 2012 at 10:04 AM, Destin Zed wrote:
> Hello Helena,
>
> It seems we are experiencing the same problem. I was about to post it. I have attempted it in the following way but there is still no guarantee that x and the binary variable are properly associated.
> y = s1(a1x + b1) + s2(a2x + b2) + s3(a3x + b3)
> where s1 + s2 + s3 = 1.
>
> To linearize the above equation, I used the disjunctive formulation:
>
> -L*(1 - si) s1+s2+s3 = 1
>
> where si = s1, s2, s3 and ai and bi are the constants in your formulation ,
> U = max ( ai*x + bi) and L = min (ai*x + bi), (i = 1, 2, 3)
>
> This is not still the perfect solution.
>
> Fellow GAMSERS, please help both of us.
>
> Bests,
> Destin
>
>
> On Thu, Mar 22, 2012 at 6:31 AM, helena wrote:
> Dear all, sorry to bother you, I have a question about defining
> multiple binary variables. I need to split x-axis into three pieces ,
> so when x falls within the range from 0 to like 100, the first binary
> S1 will be 1 and the equation will be "y=a1*x+b1"; and if x falls
> within the range from 100 to for example 200, the second binary S2
> will be 1 and the relation of y and x will be " y=a2*x +b2"; and when
> x falls within the rest range of X-axis, the third binary S3 will be 1
> and " y=a3*x+b3". and X can only fall in one range, that is to say,
> S1+S2+S3=1;
>
> So my question is , how to let gams know which x is associated with
> which binary. PS: I can only use Cplex to solve this mip so I can't
> use if-statement.
>
> Looking forward to your reply.
> Best regards,
> Helena
>
> --
> To post to this group, send email to gams...@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
>
>
>
> --
> To post to this group, send email to gams...@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
>
>
>
> --
> To post to this group, send email to gams...@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
>
>
> --
> To post to this group, send email to gams...@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
>
>
> --
> To post to this group, send email to gams...@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.
>
>
> --
> To post to this group, send email to gams...@googlegroups.com.
> To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

--
To post to this group, send email to gams...@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.


--
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at https://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.