[AMPL 2631] Arbitrary Cartesian Products

[Guilherme Freitas]

Hi  everybody. I need to evaluate a function over a set like this:

{ (r_1, ..., r_L)  :  r_1 <= n_1, ..., r_L <= n_L  and  sum {i in
1, ..., L} r_i = k }

where L, n1, ..., n_L and k are positive integers ('params') defined
by data. The problem is that I don't know how to write the set above
in AMPL. I looked in the book for a while, but couldn't find anything
helpful. I would be very grateful if someone could point out the page
in the book where this is explained or post the code to write this
set.

Thanks in advance,

--Guilherme Freitas

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

[Guilherme Freitas]

Ok, I came up with a possible solution, but it is not working. The
idea is to use recursion to construct the cartesian products and use
'setof' to obtain the final desired set, which is:

PivotalVotes = { (r_1, ..., r_L)  :  r_1 <= n_1, ..., r_L <= n_L  and
sum {i in 1, ..., L} r_i = k }

The code is below, but if it helps reading it, here is the story:
there is a set of 'Parties', of cardinality 'L', and for each party
'l' there is a number of legislators 'n[l]'. The total number of
legislators is 'N', and to pass some piece of legislation, the
fraction of 'yes' votes must be greater than some fraction/quota 'q'.
That is, more than 'floor(N*q)' votes are needed. We want to define
the set of all possible combinations '(r1, ..., rL)' of 'yes' votes
(for example, (3,4) would be a configuration of 3 'yes' from the first
party, and 4 'yes' from the second party) such that the total number
of 'yes' is equal to 'floor(N*q)', that is, only one more 'yes' is
required pass the legislation. This set should be the set
'PivotalVotes' displayed above (same name in the code below).

The problems I'm having with the code (in the end of the message)
right now are the following:

1. If I import this code up to the definition of set 'C' (excluding
'D' and 'PivotalVotes') and create some data for it (Parties =
{Republicans, Democrats}), when I run 'display C', I get the following
error message:

Error executing "display" command:
        can't convert 'Democrat' to a number.

I think the problem is when 'C[s-1]' is called (see code). I guess all
I need to do is to do everything in terms of numbers, not parties,
right? But I would like to keep the identity of the parties in the
code, and I would like to understand why the code below does not
define 'C' as I wanted.

2. If I import all of this code (saved as 'test.txt') and create some
data for it, I get an error when running 'model test.txt;':

ampl: model test.txt;

test.txt, line 12 (offset 409):
        syntax error
context:  set PivotalVotes = setof {r in D, i in {1..L}:  >>> r[ <<<
i] <= n[i] and


Can anyone help?

Thanks in advance,

Guilherme


---- begin code ----

set Parties ordered;   # Set of political parties
param L = card(Parties);   # Number of parties
param n {Parties} integer > 0;   # number of legislators in each party

param N = sum {l in Parties} n[l]
param q;

set C {s in Parties} =    # auxiliary set
  if s == first(Parties)
    then {1..n[first(Parties)]}
  else C[s-1] cross {1..n[member(s, Parties)]};

set D = C[last(Parties)];   # auxiliary set

set PivotalVotes = setof {r in D, i in {1..L} : r[i] <= n[i] and
   sum {j in 1..L} r[j] = floor(N*q)} r;



# Set of pivotal votes. Auxiliar for the 'Prpiv' variable

set PivotalVotes = setof {r in D, i in {1..L}: r[i] <= n[i] and
  sum {j in 1..L} r[j] = nq} r;

---- end code ----

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

[Guilherme Freitas]

Ok, I think I have cornered the problem (even though I don't know if
there is a solution). I have created some files (all posted in the
end):

- 'test1.mod': exposes part of the problem
- 'test2.mod': exposes another part of the problem
- 'test.dat': a simple data file
- 'test.run': a commands file to show all the problems

Just run 'test.run' and you should see the problem. But I also found
another thread in this mailing list that argues that what I want to do
is impossible in AMPL:

http://groups.google.com/group/ampl/browse_thread/thread/32d801bcd702bff4/5952ab6a36672f41?lnk=gst&q=cartesian#5952ab6a36672f41

I usually look at the history of the list before asking, and I really
thought I had searched this list before asking. Anyway. Is there any
hope that a feature to solve this problem will be implemented in the
future? Why AMPL does not do it? Is it particularly difficult to
implement? Bob Fourer mentioned that there may be workarounds in
special cases; is there a workaround for my case?

Best,

Guilherme

---begin test1.mod---
set Parties ordered;   # Set of political parties
param L = card(Parties);   # Number of parties
param n {Parties} integer > 0;   # number of legislators in each party

set C {s in 1..L} =    # auxiliary set
  if s == 1
    then 1..n[first(Parties)]
  else C[s-1] cross 1..n[member(s, Parties)];

set D = C[L];   # auxiliary set

---end test1.mod---

---begin test2.mod---
set Parties ordered;   # Set of political parties
param L = card(Parties);   # Number of parties
param n {Parties} integer > 0;   # number of legislators in each party

set C {s in 1..L} =    # auxiliary set
  if s == 1
    then 1..n[first(Parties)]
  else 1..n[member(1, Parties)] cross 1..n[member(s, Parties)];

set D = C[L];   # auxiliary set

---end test2.mod---

---begin test.dat---
set Parties = Republican, Democrat;

param n :=
Republican 2
Democrat 3 ;

---end test.dat---

---begin test.run---
model test1.mod;
data test.dat;

print "Displaying D: should be {1, 2} x {1, 2, 3}";
display D;

print "Building D by hand to check if commands make sense. Name it
E.";
set E = 1..n[first(Parties)] cross 1..n[member(2, Parties)];
display E;

print "Cheating the recursion that defines 'C' and exposing the
problem:";
reset;
model test2.mod;

---end test.run---

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

[Paul A. Rubin]

On Jul 9, 4:21 am, Guilherme Freitas <guilhe...@...> wrote:

> Hi  everybody. I need to evaluate a function over a set like this:
>
> { (r_1, ..., r_L)  :  r_1 <= n_1, ..., r_L <= n_L  and  sum {i in
> 1, ..., L} r_i = k }
>
> where L, n1, ..., n_L and k are positive integers ('params') defined
> by data. The problem is that I don't know how to write the set above
> in AMPL. I looked in the book for a while, but couldn't find anything
> helpful. I would be very grateful if someone could point out the page
> in the book where this is explained or post the code to write this
> set.
>

You did not specify lower limits for r_1, r_2 etc.; I'm assuming you
want them >= 1 (but >= 0 is an easy adjustment).

I'm not sure you can do this with L as a parameter.  With L as a
constant it can be done.  Suppose L=3.  The following should work:

param n {1..L} integer > 0;
param k integer > 0;
# ...
set S := setof {(r1,r2,r3) in 1..n[1] cross 1..n[2] cross 1..n[3] : r1
+ r2 + r3 == k};
# now index your function over S

Unfortunately, AMPL tends to be rather finicky about set arity (in
particular, I don't think you can declare an array of sets where each
set has a different arity), and at least in the (rather old) version
that I have, the cross operator cannot be indexed.

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

[Robert Fourer-2]

The dimension (or arity) of a set cannot depend on a data value.  Hence you
can make this work, as Paul suggests, when L is a fixed number, but not when
L is an integer parameter whose value is given in the data.  Indeed the
latter would require a substantial extension to AMPL's indexing expressions;
for example the number of "subscripts" in an expression like X[i1,i2,i3]
would not be known when the expression was parsed but would instead depend
on the data.

To enumerate all possible tuples (r_1, ..., r_L) having some property like
this, I have taken the following approach.  I let the tuples be numbered
arbitrarily from 1 to N, and define "param tuple_list {1..L,1..N};" where
tuple_list[i,j] is the value of r_i in the jth tuple.  I set N to some upper
limit (depending on L) on the number of tuples that will be generated, and
then write some for loops to compute all the possible tuples.  It does take
some thought to figure out how to do the for loops efficiently, though;
writing L nested for loops will not work, since L depends on the data.

Also possibly if L does not get very large then you could just write a
different model or script for each different value of L.

Bob Fourer
4er@...

> -----Original Message-----
> From: ampl@... [mailto:ampl@...]
> On Behalf Of Guilherme Freitas [guilherme@...]
> Sent: Thursday, July 09, 2009 3:21 AM
> To: AMPL Modeling Language
> Subject: [AMPL 2631] Arbitrary Cartesian Products
>
>
> Hi  everybody. I need to evaluate a function over a set like this:
>
> { (r_1, ..., r_L)  :  r_1 <= n_1, ..., r_L <= n_L  and  sum {i in
> 1, ..., L} r_i = k }
>
> where L, n1, ..., n_L and k are positive integers ('params') defined
> by data. The problem is that I don't know how to write the set above
> in AMPL. I looked in the book for a while, but couldn't find anything
> helpful. I would be very grateful if someone could point out the page
> in the book where this is explained or post the code to write this
> set.
>
> Thanks in advance,
>
> --Guilherme Freitas
>

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

[Guilherme Freitas]

Robert, Paul, thanks for the answers.

As I cannot automate this in the AMPL code, I will just write a little
program that generates the AMPL code for each program. In a sense, it
is a shame, because AMPL code is *very* readable, and I saw no need to
write a pretty interface for it to let my co-authors run their
numerical experiments; they could just create their data files. Now if
I have to write a program (a Python script) to generate AMPL code,
they will have interact with this script somehow, and then I will need
to worry about the interface.

Anyway, thanks for the answers.

Best,

Guilherme



On Jul 12, 1:52 am, Guilherme Freitas <guilhe...@...> wrote:

> Ok, I think I have cornered the problem (even though I don't know if
> there is a solution). I have created some files (all posted in the
> end):
>
> - 'test1.mod': exposes part of the problem
> - 'test2.mod': exposes another part of the problem
> - 'test.dat': a simple data file
> - 'test.run': a commands file to show all the problems
>
> Just run 'test.run' and you should see the problem. But I also found
> another thread in this mailing list that argues that what I want to do
> is impossible in AMPL:
>
> http://groups.google.com/group/ampl/browse_thread/thread/32d801bcd702...
>
> I usually look at the history of the list before asking, and I really
> thought I had searched this list before asking. Anyway. Is there any
> hope that a feature to solve this problem will be implemented in the
> future? Why AMPL does not do it? Is it particularly difficult to
> implement? Bob Fourer mentioned that there may be workarounds in
> special cases; is there a workaround for my case?
>
> Best,
>
> Guilherme
>
> ---begin test1.mod---
> set Parties ordered;   # Set of political parties
> param L = card(Parties);   # Number of parties
> param n {Parties} integer > 0;   # number of legislators in each party
>
> set C {s in 1..L} =    # auxiliary set
>   if s == 1
>     then 1..n[first(Parties)]
>   else C[s-1] cross 1..n[member(s, Parties)];
>
> set D = C[L];   # auxiliary set
>
> ---end test1.mod---
>
> ---begin test2.mod---
> set Parties ordered;   # Set of political parties
> param L = card(Parties);   # Number of parties
> param n {Parties} integer > 0;   # number of legislators in each party
>
> set C {s in 1..L} =    # auxiliary set
>   if s == 1
>     then 1..n[first(Parties)]
>   else 1..n[member(1, Parties)] cross 1..n[member(s, Parties)];
>
> set D = C[L];   # auxiliary set
>
> ---end test2.mod---
>
> ---begin test.dat---
> set Parties = Republican, Democrat;
>
> param n :=
> Republican 2
> Democrat 3 ;
>
> ---end test.dat---
>
> ---begin test.run---
> model test1.mod;
> data test.dat;
>
> print "Displaying D: should be {1, 2} x {1, 2, 3}";
> display D;
>
> print "Building D by hand to check if commands make sense. Name it
> E.";
> set E = 1..n[first(Parties)] cross 1..n[member(2, Parties)];
> display E;
>
> print "Cheating the recursion that defines 'C' and exposing the
> problem:";
> reset;
> model test2.mod;
>
> ---end test.run---

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

[Robert Fourer-2]

You need a for-loop to do this.  For example when L is 2,

   param r {i in 1..N, j in 1..L};
   param j;

   let j := 0;
   for {(r1,r2) in PivotalVotes} {
      let j := j + 1;
      let r[j,1] := r1;
      let r[j,2] := r2;
   }

When L is 3 you have to expand the loop,

   for {(r1,r2,r3) in PivotalVotes} {
      let j := j + 1;
      let r[j,1] := r1;
      let r[j,2] := r2;
      let r[j,3] := r3;
   }

There's no way to write a general loop that handles every possible value of
L, as that would again involve working with a set (PivotalVotes) and with
tuples whose dimension depends on a data value.

Bob Fourer
4er@...

> -----Original Message-----
> From: guilherme.freitas@... [mailto:guilherme.freitas@...] On
> Behalf Of Guilherme P. de Freitas
> Sent: Sunday, July 12, 2009 7:21 PM
> To: 4er@...
> Cc: ampl@...
> Subject: Re: [AMPL 2631] Arbitrary Cartesian Products
>
> I guess the short question is: if 'a' is a tuple, how do I specify the
> j-th element of 'a'?
>
> On Sun, Jul 12, 2009 at 5:11 PM, Guilherme P. de
> Freitas<guilherme@...> wrote:
> > It turns out that if I rewrite that 'PivotalVotes' set by hand, then I
> > have to create a "number-of-parties-agnostic" representation of it for
> > later use, otherwise I will also have to rewrite almost everything
> > that follows the definition of the set "PivotalVotes" for every
> > different problem. I am trying to do what Robert Fourer suggested,
> > creating a parameter 'r' indexed by {1..N, 1..L} where N is the total
> > number of qualifying tuples (r1, ..., rL) and L is the number of
> > parties, and 'r[i, j]' should be the value of 'rj' (written by hand in
> > the definition of PivotalVotes, note that 'rj' is different from
> > 'r[j]') in the 'i-th' qualifying tuple. So I am trying this (example
> > with L=2 parties):
> >
> > \\--- begin code ---
> >
> > set Parties ordered;   # Set of political parties
> > param L = card(Parties);   # Number of parties
> > param n {Parties} integer > 0;   # number of legislators in each party
> > param n_total = sum {party in Parties} n[party];    # total number of
> > legislators
> > param q;     # fraction of votes necessary for legislation to pass
> >
> > set auxC = {0..n[member(1, Parties)], 0..n[member(2, Parties)]};
> >
> > set PivotalVotes = {(r1, r2) in auxC : r1 + r2 = floor(n_total * q)}
> > ordered;  # combinations of votes such that one more vote passes the
> > legislation
> >
> > param N = card(PivotalVotes);
> >
> > param r {i in 1..N, j in 1..L} = member(i, PivotalVotes)[j]
> >
> > --- end code ---//
> >
> > But the problem is that "member(i, PivotalVotes)[j]" is illegal
> > syntax. But I need a way to select the l-th member of a tuple.
> > Otherwise this code will be too messy.
> >
> > Thanks in advance,
> >
> > Guilherme
> >

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

[Guilherme Freitas]

Thanks. I will implement something like this.

--
Guilherme P. de Freitas
http://www.gpfreitas.com

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