Automatically generating subsets of a set

[niki matinrad]

Hi,

I have a set I={1,...,N} and in one of my constraints I want that for a given value of m (m member of I and m >=2) a set K:=1..(m-1) forms that all of its subsets (S) can form and be used. The constraint in mathematical formulation looks this way, and only x's are variables:

For example, if I={1,...,10} for a m=4, K should become {1,2,3} and all of its combinations should be used, one at a time, for S ((1), (2), (3), (1,2), (1,3), (2,3), (1,2,3)). 

I'm not sure if declaring the sets as below would work:

set K;

set K:=1..(m-1); 

set S within K;

Or writing the constraint in AMPL as below is the right way:

Constraint {m in I, S within K, ta[s] in J, tb[s] in J: m >= 2} and ta[s] <> tb[s]}: p_hat[m] <= p[m] * prod{s in S}(1-a*pro[j_s[s], ta[s]]) + sum{s in S} x[s, tb[s]] + sum{s in S} (1 - x[s, ta[s]]) + sum{j in J, r in (K diff S)}x[r,j];

with these declared:

set K;

set K:=1..(m-1); 

Is it even possible to do have dynamic sets in AMPL and if so how to write such constraint in AMPL with proper syntax?

Best,

Niki

[AMPL Google Group]

AMPL only has indexing over members of sets, not over subsets of sets. So in AMPL you need to take an indirect approach to formulating these constraints.

A discussion of indexing over every subset of a set is given in the AMPL Frequently Asked Questions. Read the discussion in How can I get AMPL to index over the “power set” consisting of all subsets of a set? and also look at the at the example tsp.mod given there.

Also if you search at https://groups.google.com/group/ampl for "power set" you will find answers to related questions about indexing over all subsets of a set.

--
Robert Fourer
am...@googlegroups.com

{#HS:1433111252-101311#}

[niki matinrad]

Thank you very much for your response, the links, and giving me a direction to look for my needed answer!

Best,

Niki

[niki matinrad]

Hi,

I have two follow up questions.

First question is about the sets SS and POW. As described in https://ampl.com/faqs/how-can-i-get-ampl-to-index-over-the-power-set-consisting-of-all-subsets-of-a-set/ as well as some examples I was expecting that for a set S of for instance size 4, SS will be of size 16 (with the empty subset). However, when I tried it to see how it looks, SS has 31 members, and from POW I could see that each subset is repeated twice. You can see the result below. Have I misunderstood somethings, or done somethings wrong? Why each subset is created twice? 

and this is what I used in AMPL:

param n := 5;

set S := 1..(n-1);

set SS := 1 .. (2**n - 1);

set POW {k in SS} := {i in S: (k div 2**i) mod 2 == 1};

My other question is related to the set S that I need to use in my constraint. In all examples that I saw (to the extent that I found examples), all of them work with one set S and its subsets. However, in my constraint, set S (shown with K) is formed for each value of m; therefore, if set I (m in I, m>=2) in one case has 5 members to iterate through, S (K in my constraint) should be formed four times and SS should be formed for each time S is formed. By defining n and set as written above, only one of the four S's is formed and subsequently its subsets. Is there a way to pass values to parameter "n" from inside the constraint's definition so that all S's, SS's, and POW's can form for each value of "m" in the constraint?

I really appreciate your help and any suggestion or advice.

Regards

Niki

[AMPL Google Group]

The example in the FAQ has "set S := 0 .. n - 1;" but you have "set S := 1..(n-1);". If you make that change, then you need to change the other statements accordingly:

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

Once you have defined POW like this, for any 2 <= m <= 4 the subsets of 1..m are given by POW[1] through POW[2^m-1].

--
Robert Fourer
am...@googlegroups.com

{#HS:1433111252-101311#}

On Thu, Feb 25, 2021 at 1:31 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi,

I have two follow up questions.

First question is about the sets SS and POW. As described in https://ampl.com/faqs/how-can-i-get-ampl-to-index-over-the-power-set-consisting-of-all-subsets-of-a-set/ as well as some examples I was expecting that for a set S of for instance size 4, SS will be of size 16 (with the empty subset). However, when I tried it to see how it looks, SS has 31 members, and from POW I could see that each subset is repeated twice. You can see the result below. Have I misunderstood somethings, or done somethings wrong? Why each subset is created twice?

and this is what I used in AMPL:

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

My other question is related to the set S that I need to use in my constraint. In all examples that I saw (to the extent that I found examples), all of them work with one set S and its subsets. However, in my constraint, set S (shown with K) is formed for each value of m; therefore, if set I (m in I, m>=2) in one case has 5 members to iterate through, S (K in my constraint) should be formed four times and SS should be formed for each time S is formed. By defining n and set as written above, only one of the four S's is formed and subsequently its subsets. Is there a way to pass values to parameter "n" from inside the constraint's definition so that all S's, SS's, and POW's can form for each value of "m" in the constraint?

I really appreciate your help and any suggestion or advice.

Regards
Niki

On Mon, Feb 22, 2021 at 7:38 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Thank you very much for your response, the links, and giving me a direction to look for my needed answer!

Best,
Niki

On Mon, Feb 22, 2021 at 6:18 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

AMPL only has indexing over members of sets, not over subsets of sets. So in AMPL you need to take an indirect approach to formulating these constraints.

A discussion of indexing over every subset of a set is given in the AMPL Frequently Asked Questions. Read the discussion in How can I get AMPL to index over the “power set” consisting of all subsets of a set? and also look at the at the example tsp.mod given there.

Also if you search at https://groups.google.com/group/ampl for "power set" you will find answers to related questions about indexing over all subsets of a set.

--
Robert Fourer
am...@googlegroups.com

[niki matinrad]

Ok, I see; now I understand the mistake I made.

Thank you very much for your answers.

[Gaetano Di Felice]

Hi, Could i ask you how did you eliminate the repeted twice subsets? I have the same problem, Thank you! 

[AMPL Google Group]

The example in the FAQ works when you define "set S := 0..(n-1);". But if you have "set S := 1..(n-1);" then the example in the FAQ will genrrate each sset twice. Instead you need to use the modified code that I gave in my previous reply:

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

--
Robert Fourer
am...@googlegroups.com

{#HS:1433111252-101311#}

On Tue, Jul 26, 2022 at 11:43 AM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi, Could i ask you how did you eliminate the repeted twice subsets? I have the same problem, Thank you!

On Fri, Feb 26, 2021 at 1:51 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Ok, I see; now I understand the mistake I made.

Thank you very much for your answers.

On Thu, Feb 25, 2021 at 11:05 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

The example in the FAQ has "set S := 0 .. n - 1;" but you have "set S := 1..(n-1);". If you make that change, then you need to change the other statements accordingly:

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

Once you have defined POW like this, for any 2 <= m <= 4 the subsets of 1..m are given by POW[1] through POW[2^m-1].

--
Robert Fourer
am...@googlegroups.com