RE: [Help-glpk] Building set of sets from plain set

[Robert Fourer]

> -----Original Message-----
> From: address@hidden [mailto:help-glpk-
> address@hidden On Behalf Of Andrew Makhorin
> Sent: Tuesday, December 09, 2008 11:55 PM
> To: Meketon, Marc
> Cc: address@hidden
> Subject: Re: [Help-glpk] Building set of sets from plain set
> 
> > AMPL has specific arc/node based variables and constraints that are
> > similar to your example (see example below).  Seems like this also
> > allows efficient sparse network generation.
> 
> > set V;
> > set E within (V cross V);
> 
> > param cost {E} >= 0;      # shipment costs per ton
> 
> > minimize Total_Cost;
> 
> > node Supply {k in V}: net_out = 0;
> > node Demand {k in V}: net_in = 0;
> 
> > arc Ship {(i,j) in E} >= 0, <= link_cap[i,j],
> >    from Demand[i], to Supply[j], obj Total_Cost cost[i,j];
> 
> > arc Through {k in V} >= 0, <= city_cap[k],
> >    from Supply[k], to Demand[k];
> 
> Thank you for information.
> 
> Yes, this Ampl feature looks like an attempt to specify some
> constraints by columns rather than by rows that is more efficient in
> case of network models. Or may be due to network solvers.
> 
> However, this Ampl feature seems to me quite artificial. I would not
> like to be limited only by network models. The feature which I plan to
> include in Mathprog is much more general and able to cover network
> models as a particular case of lp problems.
> 

The "node" and "arc" declarations in AMPL were mainly included in order to
allow network models to be formulated more nearly in the way that people think
about them.  Efficiency was a secondary concern, as the AMPL processor is fast
on network problems even when they are specified by row (via explicit flow in =
flow out constraints).  This is discussed in detail in
www.ampl.com/REFS/spestruc.pdf.

Formulation "by column" in AMPL is not limited to network problems, moreover.
The coefficients of any linear program can be specified in a column-wise
fashion.  This is described in the chapter on Columnwise Formulations in the
AMPL book and also in the above-cited report.

Bob Fourer
address@hidden