[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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-----
From: address@hidden
[mailto:address@hidden On
Behalf Of Andrew Makhorin
Sent: Tuesday, December 09, 2008 11:22 PM
To: Andrew Makhorin
Cc: address@hidden
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

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
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. 

Thank you for your cooperation.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]