User Tools

Site Tools


gams:formulate_a_power_set

How do I formulate a power set?

Q: Is it possible to create a set that has an index? In my problem, I need to create a constraint for every possible subset of nodes. I have found some code that allows me to create all the subsets (copied below) . What I would like to do is assign each subset to an index (i.e. W(1) = “subset 1”, W(2)=“setset 2”, etc.). Then after all the subsets are found (and assigned to an index of W), I could create the constraint using each W.

Please find below some code to compute and display a power set. Is this what you were looking for?

$eval n 6
$eval M power(2,%n%)
sets
  i 'Nodes'    / i1 * i%n% /
  c 'enumerate the power set of i'  / 1 * %M% /
  ps(c,i) 'power set of i'
  ;
scalar j;
loop {c,
   j = ord(c) - 1;
   loop {i,
       ps(c,i) = mod(j, 2);
       j = floor(j / 2);
   }
}
display ps;

This code will be slow for large sets because of the assignment to ps(c,i) where c is huge and appears in a loop (there is no search record to help the search for the insert position). Here is another implementation provided by Arne Drud, which is a little bit more difficult to read much but much faster for larger sets (e.g. n 22):

$eval n 6
$eval M power(2,%n%)
sets
  i 'Nodes'    / i1 * i%n% /
  c 'enumerate the power set of i'  / 1 * %M% /
  ps(c,i) 'power set of i'
  ;
parameter num(c), num2(c);
num(c) = ord(c)-1;
loop {i,
   num2(c) = floor( num(c)/2 );
   ps(c,i) = num2(c)*2 ne num(c);
   num(c)  = num2(c);
}
display ps;
----     17 SET ps  power set of i

            i1          i2          i3          i4          i5          i6

2          YES
3                      YES
4          YES         YES
5                                  YES
6          YES                     YES
7                      YES         YES
8          YES         YES         YES
9                                              YES
10         YES                                 YES
11                     YES                     YES
12         YES         YES                     YES
13                                 YES         YES
14         YES                     YES         YES
15                     YES         YES         YES
16         YES         YES         YES         YES
17                                                         YES
18         YES                                             YES
19                     YES                                 YES
20         YES         YES                                 YES
21                                 YES                     YES
22         YES                     YES                     YES
23                     YES         YES                     YES
24         YES         YES         YES                     YES
25                                             YES         YES
26         YES                                 YES         YES
27                     YES                     YES         YES
28         YES         YES                     YES         YES
29                                 YES         YES         YES
30         YES                     YES         YES         YES
31                     YES         YES         YES         YES
32         YES         YES         YES         YES         YES
33                                                                     YES
34         YES                                                         YES
35                     YES                                             YES
36         YES         YES                                             YES
37                                 YES                                 YES
38         YES                     YES                                 YES
39                     YES         YES                                 YES
40         YES         YES         YES                                 YES
41                                             YES                     YES
42         YES                                 YES                     YES
43                     YES                     YES                     YES
44         YES         YES                     YES                     YES
45                                 YES         YES                     YES
46         YES                     YES         YES                     YES
47                     YES         YES         YES                     YES
48         YES         YES         YES         YES                     YES
49                                                         YES         YES
50         YES                                             YES         YES
51                     YES                                 YES         YES
52         YES         YES                                 YES         YES
53                                 YES                     YES         YES
54         YES                     YES                     YES         YES
55                     YES         YES                     YES         YES
56         YES         YES         YES                     YES         YES
57                                             YES         YES         YES
58         YES                                 YES         YES         YES
59                     YES                     YES         YES         YES
60         YES         YES                     YES         YES         YES
61                                 YES         YES         YES         YES
62         YES                     YES         YES         YES         YES
63                     YES         YES         YES         YES         YES
64         YES         YES         YES         YES         YES         YES
gams/formulate_a_power_set.txt · Last modified: 2012/01/10 13:58 by support