TRY NOW!
AMPL > >Sets and Indexing > >How can I get AMPL to index over the “power set” consisting of all subsets of a set?

AMPL can index model components by objects (numbers and character strings) but not by sets of objects. Hence you can’t model a power set directly. You may be able to get the same effect, however, by constructing a numbered list of subsets.

As an example, suppose that you want to index over all subsets of the set of the first n nonnegative integers. You can declare:

param n integer > 0;
set S := 0 .. n - 1;
set SS := 0 .. 2**n - 1;
set POW {k in SS} := {i in S: (k div 2**i) mod 2 = 1};

Since there are n members of S, there are 2**n subsets of S. Hence there exists a one-to-one correspondence between the members of the set SS := 0 .. 2**n - 1 and the subsets of S. By use of a simple encoding, you can make this correspondence explicit; the indexed collection of sets POW above is declared such that POW[k] is the kth distinct subset of S. (To see the whole power set, type display POW.)

Much the same can be done for an arbitrary ordered set S:

set S ordered;
param n := card {S};
set SS := 0 .. (2**n - 1);
set POW {k in SS}
   := {i in S: (k div 2**(ord(i)-1)) mod 2 = 1};

Either way, you can use indexing over POW to get the effect of indexing over the power set. In the following example, each member s of S has a weight Wt[s], and the average “weight” of all members of any subset of S is constrained not to exceed n/2:

var Wt {S} >= 0;
subj to MaxWt {k in SS}:
   sum {i in POW[k]} Wt[i] <= (n / 2) * card(POW[k]);

A more involved example, which represents a traveling salesman problem as an integer program, is provided in tsp.mod. Constraints like this can be useful for studying and testing certain formulations of combinatorial problems, provided that the underlying set (S in our example) is kept to a reasonably small size.

Posted in: Sets and Indexing