Originally posted by: kasm

Hello everyone,

I am a new user of OPL and OPL Script and also new in this forum. So excuse me if my post is related to a previous topic.

I would like to implement a powerset algorithm using OPL but I do not succeed to correctly represent the output type of the function, which should be a set of sets of integerger. I have learned that we can define set of anytype of data but when I tried using set of integer as a type, like for tuple, it does not work.

Can anyone here help me to handle this problem? do you have any other idea of how to solve it?

BTW, a powerset of a set S is a function which returns all the subsets of the set S. http://en.wikipedia.org/wiki/Power_set

Thank you for your answers

Originally posted by: fbahr

Something like

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

should work.

--fbahr

Hi,

indeed your way fbahr is more efficient that what I suggested at

https://www.ibm.com/developerworks/community/forums/html/topic?id=2ca9cc74-f030-46ae-8c32-82156cfa2cd4#a32bb643-ae67-4675-a02b-9206d595d15c

and can be rewritten in OPL as

{string} s={"A","B","C","D"};
range r=1.. ftoi(pow(2,card(s)));
{string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)};

execute
{
 writeln(s2);
}

regards

Originally posted by: heidizh

Hi, 

It returns  all the subsets of the set S, but what if I only want the subsets which is more than two elements and less than |S|-1 elements?

Thank you for your answers.

Best wishes,

Heidi

Hi,

{string} s={"A","B","C","D"};
range r=1.. ftoi(pow(2,card(s)));
{string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)};

execute
{
 writeln(s2);
}

 // more than two elements and less than |S|-1 elements
 
 tuple t
 {
 {string} set;
 };
 
 {t} res={<s2[k]> | k in r : 2<=card(s2[k])<=card(s)-1};
 
 execute
 {
 writeln(res);  
 }

will work.

Regards

Originally posted by: max__x

Dear Alex, 

The code you give works, but can you make a small example and explain how to get all the subsets?  actually, I dont understand the code 

{string} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)};

Thank you

Hi,

k is the index of the set between 1 and 2 power card(s)

And then for all k, I use div and pow in order to turn k into its binary decomposition which will tell for all k and for all i in s whether i should be in the set or not.

Regards

Originally posted by: nouira

Hello Alexis,

I need to define a subassembly of a range set N={1,..n} on opl such, Q is a subset or equal to N. it is about a subtour elimination in VRP problem.

I tried this

{int} s ={1,2,3,4,5,6};
range r=1.. ftoi(pow(2,card(s)));
{int} s2 [k in r] = {i | i in s: ((k div (ftoi(pow(2,(ord(s,i))))) mod 2) == 1)};

Subtour elimination constraint

 forall (s2, k in Vehicles, d in Day)
   sum (i,j in s)x[d][i][j][k]<=card(s)-1;

but it doesn't works

Hi

see the first example in https://www.ibm.com/developerworks/community/forums/html/topic?id=f58daf79-f752-48e4-8f25-54b2f6f71b40&ps=25

regards

https://www.linkedin.com/pulse/how-opl-alex-fleischer/

nouira, are you sure you got this right? At first glance I think you need 's2' instead of 's' in your constraint?

Originally posted by: nouira

hi

when i put card(s2) it mention that function card(int) doesn't exist

That points at another problem in your code:

 forall (s2, k in Vehicles, d in Day)
   sum (i,j in s)x[d][i][j][k]<=card(s)-1;

I think you don't want s2 to be in Vehicles. What you want instead is some subset S of s2, right? Something like this

 forall (S in s2, k in Vehicles, d in Day)
   sum (i,j in S)x[d][i][j][k]<=card(S)-1;

Did you look at the link that Alex posted? It has spelled out all the details and should be very simple to copy and paste.