|
|
 | | From: | alean | | Subject: | using min operator in AMPL | | Date: | 12 Jan 2005 02:45:00 -0800 |
|
|
 | Hello,
This might be a classic question with a standard answer.
I am tring to model in AMPL the following problem:
var a,b,c,d;
minimize ... + d
such that: d=min(a,b);
.....
If instead of the min operator is the max, I can handle it easy:
minimize ... +d
such that d>=a;
d>=b;
The constraint forces d>=max(a,b) and the objective makes d=max(a,b).
Unfortunatelly it does not work the same way for the min operator.
I also tried to use the fact that min(a,b)=1/2(abs(a+b)-abs(a-b)).
Again no luck, since I will have -abs(a-b) in the objective and I
cannot eliminate the abs function (because of the minus sign).
Is there a hack aroung the usage of min in a constraint when the
objective is also to minimize ?
Thank you for the eventual tips.
Alexandru
|
|
| | From: | Brian Borchers | | Subject: | Re: using min operator in AMPL | | Date: | Wed, 12 Jan 2005 19:19:05 +0000 (UTC) |
|
|
|
"alean" wrote:
>This might be a classic question with a standard answer.
>I am tring to model in AMPL the following problem:
>
>var a,b,c,d;
>
>minimize ... + d
>such that: d=min(a,b);
Unfortunately this cannot be encoded in a linear programming problem,
since the objective function of a (minimization) linear programming
problem is always convex and your objective function is non-convex.
To see this graphically, try plotting
f(x1,x2)=min(x1,x2)
for x1>=0, x2>=0. You'll quickly see that the function is non-convex.
These kinds of problems can be handled by adding 0-1 integer
variables.
--
Brian Borchers borchers@nmt.edu
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: 505-835-5813
Socorro, NM 87801 FAX: 505-835-5366
|
|
| | From: | Erwin Kalvelagen | | Subject: | Re: using min operator in AMPL | | Date: | Wed, 12 Jan 2005 15:26:39 GMT |
|
|
|
One way to model d = min(a,b) is:
d <= a
d <= b
d >= a - M1*y
d >= b - M2*(1-y)
y binary
where M1,M2 are carefully chosen "big-M" constants
(choose as small as possible).
----------------------------------------------------------------
Erwin Kalvelagen
GAMS Development Corp., http://www.gams.com
erwin@gams.com, http://www.gams.com/~erwin
----------------------------------------------------------------
On Wed, 12 Jan 2005 02:45:00 -0800, alean wrote:
> Hello,
> This might be a classic question with a standard answer.
> I am tring to model in AMPL the following problem:
>
>
> var a,b,c,d;
>
> minimize ... + d
> such that: d=min(a,b);
> ....
>
>
> If instead of the min operator is the max, I can handle it easy:
> minimize ... +d
> such that d>=a;
> d>=b;
> The constraint forces d>=max(a,b) and the objective makes d=max(a,b).
> Unfortunatelly it does not work the same way for the min operator.
>
> I also tried to use the fact that min(a,b)=1/2(abs(a+b)-abs(a-b)).
> Again no luck, since I will have -abs(a-b) in the objective and I
> cannot eliminate the abs function (because of the minus sign).
>
> Is there a hack aroung the usage of min in a constraint when the
> objective is also to minimize ?
> Thank you for the eventual tips.
> Alexandru
|
|
| | From: | alean | | Subject: | Re: using min operator in AMPL | | Date: | 12 Jan 2005 07:44:00 -0800 |
|
|
| Yes, I thought about using a binary variable. The problem is that I
have a nonlinear model and then I would need a integer nonlinear
solver.
Unfortunatelly I need a hack without integers. I am afraid that it
might not be possible.
Thanks for the reply.
Alexandru
> One way to model d = min(a,b) is:
>
> d <= a
> d <= b
> d >= a - M1*y
> d >= b - M2*(1-y)
> y binary
>
> where M1,M2 are carefully chosen "big-M" constants
> (choose as small as possible).
>
> ----------------------------------------------------------------
> Erwin Kalvelagen
> GAMS Development Corp., http://www.gams.com
> erwin@gams.com, http://www.gams.com/~erwin
> ----------------------------------------------------------------
>
> On Wed, 12 Jan 2005 02:45:00 -0800, alean wrote:
>
> > Hello,
> > This might be a classic question with a standard answer.
> > I am tring to model in AMPL the following problem:
> >
> >
> > var a,b,c,d;
> >
> > minimize ... + d
> > such that: d=min(a,b);
> > ....
> >
> >
> > If instead of the min operator is the max, I can handle it easy:
> > minimize ... +d
> > such that d>=a;
> > d>=b;
> > The constraint forces d>=max(a,b) and the objective makes
d=max(a,b).
> > Unfortunatelly it does not work the same way for the min operator.
> >
> > I also tried to use the fact that min(a,b)=1/2(abs(a+b)-abs(a-b)).
> > Again no luck, since I will have -abs(a-b) in the objective and I
> > cannot eliminate the abs function (because of the minus sign).
> >
> > Is there a hack aroung the usage of min in a constraint when the
> > objective is also to minimize ?
> > Thank you for the eventual tips.
> > Alexandru
|
|
| | From: | Erwin Kalvelagen | | Subject: | Re: using min operator in AMPL | | Date: | Wed, 12 Jan 2005 16:27:13 GMT |
|
|
|
Too bad you did not mention this in the first place.
You could use a smooth approximation, e.g.:
d = b - (1/p)*ln(1+exp[-p*(a-b)])
for some p (e.g. p=10)
----------------------------------------------------------------
Erwin Kalvelagen
GAMS Development Corp., http://www.gams.com
erwin@gams.com, http://www.gams.com/~erwin
----------------------------------------------------------------
On Wed, 12 Jan 2005 07:44:00 -0800, alean wrote:
> Yes, I thought about using a binary variable. The problem is that I
> have a nonlinear model and then I would need a integer nonlinear
> solver.
> Unfortunatelly I need a hack without integers. I am afraid that it
> might not be possible.
>
> Thanks for the reply.
> Alexandru
>
>> One way to model d = min(a,b) is:
>>
>> d <= a
>> d <= b
>> d >= a - M1*y
>> d >= b - M2*(1-y)
>> y binary
>>
>> where M1,M2 are carefully chosen "big-M" constants
>> (choose as small as possible).
>>
>> ----------------------------------------------------------------
>> Erwin Kalvelagen
>> GAMS Development Corp., http://www.gams.com
>> erwin@gams.com, http://www.gams.com/~erwin
>> ----------------------------------------------------------------
>>
>> On Wed, 12 Jan 2005 02:45:00 -0800, alean wrote:
>>
>> > Hello,
>> > This might be a classic question with a standard answer.
>> > I am tring to model in AMPL the following problem:
>> >
>> >
>> > var a,b,c,d;
>> >
>> > minimize ... + d
>> > such that: d=min(a,b);
>> > ....
>> >
>> >
>> > If instead of the min operator is the max, I can handle it easy:
>> > minimize ... +d
>> > such that d>=a;
>> > d>=b;
>> > The constraint forces d>=max(a,b) and the objective makes
> d=max(a,b).
>> > Unfortunatelly it does not work the same way for the min operator.
>> >
>> > I also tried to use the fact that min(a,b)=1/2(abs(a+b)-abs(a-b)).
>> > Again no luck, since I will have -abs(a-b) in the objective and I
>> > cannot eliminate the abs function (because of the minus sign).
>> >
>> > Is there a hack aroung the usage of min in a constraint when the
>> > objective is also to minimize ?
>> > Thank you for the eventual tips.
>> > Alexandru
|
|
|
