help-glpk
[Top][All Lists]

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

 From: Meketon, Marc Subject: RE: [Help-glpk] Building set of sets from plain set Date: Tue, 9 Dec 2008 23:57:01 -0500

```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];

-----Original Message-----
Behalf Of Andrew Makhorin
Sent: Tuesday, December 09, 2008 11:22 PM
To: Andrew Makhorin
Subject: Re: [Help-glpk] Building set of sets from plain set

>> The idea is to introduce a special operator, which is equivalent to
>> the following:

>> T[*,*] := empty;
>> for all (i,j,k,l,m) in S do
>>     T[k,i] := T[k,i] union {(j,m,l)};

>> Any suggestions about the syntax?

> Something like follows:

> set T{k in K, i in I}, data S : 3 1 : 2 5 4;

> that means that 3rd and 1st components of 5-tuple in S correspond,
> resp., to 1st and 2nd indices of T while 2nd, 5th, and 4th components
> of the 5-tuple give 3-tuple included in a plain set assigned to
> corresponding member of T.

> The statement above can be implemented as if there were data for T
> in the data section.

Just a comment.

Suppose you deal with a flow network G = (V, E), where V is a set
of nodes and E in V x V is a set of (directed) arcs. In MathProg this
may look as follows:

set V;
set E within V cross V;

To specify the flow conservation constraints you have to write:

s.t. foo{i in V}: sum{(i,j) in E} x[i,j] - sum{(j,i) in E} x[j,i] = 0;

and if E is large, evaluation of all foo[i] takes too long time.

Using the proposed feature the same constraints might be written as
follows:

set OUT{i in V}, data E : 1 : 2;
/* OUT[i] is a set of nodes incident to node i thru outgoing arcs */

set IN{i in V}, data E : 2 : 1;
/* IN[i] is a set of nodes incident to node i thru incoming arcs */

s.t. foo{i in V}: sum{j in OUT[i]) x[i,j] - sum{j in IN[i]} x[j,i] = 0;

In the latter case all foo[i] are evaluated efficiently.

_______________________________________________
Help-glpk mailing list
http://lists.gnu.org/mailman/listinfo/help-glpk
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged.  If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein.  Please inform us of the erroneous delivery by return e-mail.