linearization of maximum function

[Md. Noor-E- Alam]

Hi All:

 

I am trying to solve a LP model where I need to linearize following maximization function:

 

S[i,j]=Max (all x,y){S[i,j,x,y]};

 

Any suggestion will be highly appreciated.

 

Best Regards

 

Noor

[Paul]

How can S simultaneously have two and four indices?

Also, are x and y parameters?  (Letters at the end of the alphabet are usually used to denote variables, although that is not a firm rule.)  You cannot use variables as indices (unless you are using a constraint solver).

Paul

[Md. Noor-E- Alam]

Thanks Paul. Sorry I did not put the constraints proper way. It should be as follows:

 

S[i,j]=Max {P[i,j,x,y]*T[x,y]} for all x,y

 

Here i,j,x,y are parameters

Also P is parameter, and only T is variable

 

Thanks again.

 

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To post to this group, send email to am...@googlegroups.com.
To unsubscribe from this group, send email to ampl+uns...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ampl?hl=en.

[Paul]

On Monday, May 2, 2011 3:28:34 PM UTC-4, Noor wrote:

 

S[i,j]=Max {P[i,j,x,y]*T[x,y]} for all x,y

 

Here i,j,x,y are parameters

Also P is parameter, and only T is variable

S must also be a variable (since it's a function of variables).

set I;
set J;
set X;
set Y;
param P {I, J, X, Y};
param M > 0;  # needs to be at least as large as max P*T - min P*T
var S {I, J};
var T {X, Y};
var z {I, J, X, Y} binary;  # chooses where max occurs
# ...
s.t. SLimit {i in I, j in J, x in X, y in Y}: S[i,j] >= P[i,j,x,y]*T[x,y]; # max is >= every element in set
s.t. SWhere {i in I, j in J, x in X, y in Y}: S[i, j] <= Pi[i,j,x,y]*T[x,y] + M*(1-z[i,j,x,y]);
s.t. SOS {i in I, j in J}: sum {x in X, y in Y} z[i,j,x,y] = 1;  # one max per (i,j) pair

If the objective penalizes S and it does not appear in other constraints (so that it is clear that, regardless of whatever else is going on in the model, smaller S values are preferable), then you do not need z and the SWhere and SOS constraints; you just need the SLimit constraints.

Paul

[Md. Noor-E- Alam]

Dear Professor Paul:

I have developed my ampl model and linearized maximization function according to the following method you recommended me before. However I am experiencing computational difficulty (takes about a day or more) to solve this model for a small instances (for example i=j=x=y=7). I am doing some experiments and found that even if I relax constraint  SLimit, it gives me exactly same result (please note that in my model, I have another constraint S[i,j]>=20, and in my objective function there is no S, only minimize T). Could you please provide me any advise to overcome this difficulty.

Best Regards

Noor

[Paul]

Sorry, nothing comes to mind.

[Noor]

Thanks.I figured it out.

Sent from my iPhone

On 2012-04-28, at 8:44 PM, Paul <paru...@gmail.com> wrote:

Sorry, nothing comes to mind.

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.

To view this discussion on the web visit https://groups.google.com/d/msg/ampl/-/ikwqLw6aHzUJ.