[AMPL 2142] benders decomposition

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[AMPL 2142] benders decomposition

Kaan-2

Hi,

I am trying to implement benders decomposition for an extremely large
problem. Once I solve the dual of the subproblems, I am ready to add
necessary constraints to my master problem. So, I have defined two
problems as

problem masterp : master, mast_demand, newCE_lambda_fr2, mast_125h,
theta, const_theta;
problem subp: Zd, pi, pj, pk, sub_mc, sub_sk, sub_125;

Constraint "const_theta" looks like the following in my .mod file:

subject to const_theta{iter in 1..iter_limit}:
        theta >= 0;

where iter_limit is the number of maximum iterations.

As soon as i know the values of pi, pj and pk from my subproblems, I
would like to "add" a new const_theta, so I redeclare the iter^th
const_theta constraint and replace it in a following manner.

I have a commands file in which I write:

let iter := iter +1;
redeclare subject to const_theta[iter]:
                        theta >=sum{.... };

but ampl complains whatever I do, saying:

com.sa2, line 106 (offset 2931):
        syntax error
context:  redeclare subject to  >>> const_theta[ <<< iter]:

and I am sure i did not miss a semicolon or left something undefined
and used first.

Another idea i have is to introduce a new constraint at each iteration
without using the indexing of const_theta, but coming up with a new
name like:

subject to const_theta_iter#:
                        theta >=sum{.... };

where "iter#" will be replaced by the iteration number by result of
playing with strings. However, that brings upon a issue where I have
to declare master problem definition as:

problem masterp : master, mast_demand, newCE_lambda_fr2, mast_125h,
theta, const_theta1, const_theta2, const_theta3...;

so on so forth, where i can't think of an easy way to code that in amp
at each iteration.

So... Please help me... how can i add in new constraints in a run
file?

Thank you very much.

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

Reply | Threaded
Open this post in threaded view
|

[AMPL 2145] Re: benders decomposition

Robert Fourer-2

Kaan,

"redeclare" is not appropriate in this context.  Instead declare your
constraint as something like

   subject to const_theta {i in 1..iter}:
     theta >= sum {...} ... ;

where the formula to the right of the >= is the general expression for your
constraint; the second ... should involve the index i in some way.  Then
each time you step the parameter iter (let iter := iter +1;) a new
constraint will be generated automatically.  For an example see the
"trnloc1d" files at www.ampl.com/NEW/LOOP2, in particualar the following
constraint in the model file:

   subj to Cut_Defn {k in 1..nCUT}:
      if cut_type[k] = "point" then Max_Ship_Cost >=
         sum {i in ORIG} supply_price[i,k] * supply[i] * Build[i] +
         sum {j in DEST} demand_price[j,k] * demand[j];

[It might have been clearer to write the expression on the left as (if
cut_type[k] = "point" then Max_Ship_Cost else 0).]

Bob Fourer
[hidden email]


> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of
> Kaan
> Sent: Thursday, January 01, 2009 10:09 PM
> To: AMPL Modeling Language
> Subject: [AMPL 2142] benders decomposition
>
> Hi,
>
> I am trying to implement benders decomposition for an extremely large
> problem. Once I solve the dual of the subproblems, I am ready to add
> necessary constraints to my master problem. So, I have defined two
> problems as
>
> problem masterp : master, mast_demand, newCE_lambda_fr2, mast_125h,
> theta, const_theta;
> problem subp: Zd, pi, pj, pk, sub_mc, sub_sk, sub_125;
>
> Constraint "const_theta" looks like the following in my .mod file:
>
> subject to const_theta{iter in 1..iter_limit}:
> theta >= 0;
>
> where iter_limit is the number of maximum iterations.
>
> As soon as i know the values of pi, pj and pk from my subproblems, I
> would like to "add" a new const_theta, so I redeclare the iter^th
> const_theta constraint and replace it in a following manner.
>
> I have a commands file in which I write:
>
> let iter := iter +1;
> redeclare subject to const_theta[iter]:
> theta >=sum{.... };
>
> but ampl complains whatever I do, saying:
>
> com.sa2, line 106 (offset 2931):
> syntax error
> context:  redeclare subject to  >>> const_theta[ <<< iter]:
>
> and I am sure i did not miss a semicolon or left something undefined
> and used first.
>
> Another idea i have is to introduce a new constraint at each iteration
> without using the indexing of const_theta, but coming up with a new
> name like:
>
> subject to const_theta_iter#:
> theta >=sum{.... };
>
> where "iter#" will be replaced by the iteration number by result of
> playing with strings. However, that brings upon a issue where I have
> to declare master problem definition as:
>
> problem masterp : master, mast_demand, newCE_lambda_fr2, mast_125h,
> theta, const_theta1, const_theta2, const_theta3...;
>
> so on so forth, where i can't think of an easy way to code that in amp
> at each iteration.
>
> So... Please help me... how can i add in new constraints in a run
> file?
>
> Thank you very much.
>
> Kaan



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

Reply | Threaded
Open this post in threaded view
|

[AMPL 2147] Re: benders decomposition

Kaan-2

Thank you very much, i should have checked that webpage earlier...

Regards,

Kaan.

On Jan 2, 10:52 am, "Robert Fourer" <[hidden email]> wrote:

> Kaan,
>
> "redeclare" is not appropriate in this context.  Instead declare your
> constraint as something like
>
>    subject to const_theta {i in 1..iter}:
>      theta >= sum {...} ... ;
>
> where the formula to the right of the >= is the general expression for your
> constraint; the second ... should involve the index i in some way.  Then
> each time you step the parameter iter (let iter := iter +1;) a new
> constraint will be generated automatically.  For an example see the
> "trnloc1d" files atwww.ampl.com/NEW/LOOP2, in particualar the following
> constraint in the model file:
>
>    subj to Cut_Defn {k in 1..nCUT}:
>       if cut_type[k] = "point" then Max_Ship_Cost >=
>          sum {i in ORIG} supply_price[i,k] * supply[i] * Build[i] +
>          sum {j in DEST} demand_price[j,k] * demand[j];
>
> [It might have been clearer to write the expression on the left as (if
> cut_type[k] = "point" then Max_Ship_Cost else 0).]
>
> Bob Fourer
> [hidden email]
>
> > -----Original Message-----
> > From: [hidden email] [mailto:[hidden email]] On Behalf Of
> > Kaan
> > Sent: Thursday, January 01, 2009 10:09 PM
> > To: AMPL Modeling Language
> > Subject: [AMPL 2142] benders decomposition
>
> > Hi,
>
> > I am trying to implement benders decomposition for an extremely large
> > problem. Once I solve the dual of the subproblems, I am ready to add
> > necessary constraints to my master problem. So, I have defined two
> > problems as
>
> > problem masterp : master, mast_demand, newCE_lambda_fr2, mast_125h,
> > theta, const_theta;
> > problem subp: Zd, pi, pj, pk, sub_mc, sub_sk, sub_125;
>
> > Constraint "const_theta" looks like the following in my .mod file:
>
> > subject to const_theta{iter in 1..iter_limit}:
> >    theta >= 0;
>
> > where iter_limit is the number of maximum iterations.
>
> > As soon as i know the values of pi, pj and pk from my subproblems, I
> > would like to "add" a new const_theta, so I redeclare the iter^th
> > const_theta constraint and replace it in a following manner.
>
> > I have a commands file in which I write:
>
> > let iter := iter +1;
> > redeclare subject to const_theta[iter]:
> >                    theta >=sum{.... };
>
> > but ampl complains whatever I do, saying:
>
> > com.sa2, line 106 (offset 2931):
> >    syntax error
> > context:  redeclare subject to  >>> const_theta[ <<< iter]:
>
> > and I am sure i did not miss a semicolon or left something undefined
> > and used first.
>
> > Another idea i have is to introduce a new constraint at each iteration
> > without using the indexing of const_theta, but coming up with a new
> > name like:
>
> > subject to const_theta_iter#:
> >                    theta >=sum{.... };
>
> > where "iter#" will be replaced by the iteration number by result of
> > playing with strings. However, that brings upon a issue where I have
> > to declare master problem definition as:
>
> > problem masterp : master, mast_demand, newCE_lambda_fr2, mast_125h,
> > theta, const_theta1, const_theta2, const_theta3...;
>
> > so on so forth, where i can't think of an easy way to code that in amp
> > at each iteration.
>
> > So... Please help me... how can i add in new constraints in a run
> > file?
>
> > Thank you very much.
>
> > Kaan
>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To post to this group, send email to [hidden email]
To unsubscribe from this group, send email to [hidden email]
For more options, visit this group at http://groups.google.com/group/ampl?hl=en
-~----------~----~----~----~------~----~------~--~---