Originally posted by: Mintch Zulitch

I'm working on a group selection problem in a party-like situations. 

I have a binary variable, say y_i_j , which stands for if individual ith is in the same group of individual jth , the variable gets value one and otherwise zero.

Let me be specific:

N = number of people

I in {1,…,N}

J in {1,…,N}

For example if we have 4 people, then the binary matrix for selection of 1,3 and 2,4 is represented as follows:(means that individual number 1 and 3 are in a group and 2 and 4 are in another group). Hence we have 2 groups in total.

Or it may happen that some individuals don't want to select a partner and therefor that group gets only one individual. For example, 1 and 3 and 2,4 (hence we have 3 groups):

Now, here is my question. Which constraints should I impose to build feasible y_i_j decision variables? (from point of mathematical/integer programming)

Hi,

what you describe is a partition / equivalence set.

So you should write constraints to make sure you have an equivalence relation. (Reflexive, symetry, transitive)

int N=10;

range person=1..N;

dvar boolean y[i in person][j in person];

subject to
{
// reflexive

forall(p in person) y[p][p]==1;

// symmetry

forall(ordered p1,p2 in person) y[p1][p2]==y[p2][p1];

// transitivity

forall(p1,p2,p3 in person) ((y[p1][p2]==1) && (y[p2][p3]==1)) => y[p1][p3]==1;

}

regards

Originally posted by: Mintch Zulitch

Thank you very much Alex. You are always helpful.

I have one more question:

How can I produce all possible matrices (y) having these three relations?

and should the third constraint be changed into this:

forall(p1,p2,p3 in person) ((y[p1][p2]==1) && (y[p2][p3]==1)) => y[p1][p3]==1;

Hi,

I would write

using CP;

int N=4;

range person=1..N;

dvar boolean y[i in person][j in person];

subject to
{
// reflexive

forall(p in person) y[p][p]==1;

// symmetry

forall(ordered p1,p2 in person) y[p1][p2]==y[p2][p1];

// transitivity

forall(p1,p2,p3 in person) ((y[p1][p2]==1) && (y[p2][p3]==1)) => y[p1][p3]==1;

}

execute
{
writeln(y);
}

main
 {
   thisOplModel.generate();
   var n=0;
   cp.param.SearchType="DepthFirst";
   cp.param.Workers=1;
 cp.startNewSearch();
   while (cp.next()) {
     n++;
     writeln("solution ",n);  
     thisOplModel.postProcess();
      
   }
   
  writeln("n=",n);
   
 }   

NB: If you change N you will be abl to compute the Bell numbers ( https://en.wikipedia.org/wiki/Bell_number )

regards

Originally posted by: Mintch Zulitch

Thank you for your kindness.

This is my final question:

Is it possible to linearize the third constraint?

One simple suggestion would be:

forall(p1,p2,p3 in person:p1!=p2&&p2!=p3&&p1!=p3) y[p1][p2] + y[p2][p3] + y[p3][p1]<=2 ;

But it actually produces wrong results!

// transitivity

forall(p1,p2,p3 in person)
//((y[p1][p2]==1) && (y[p2][p3]==1)) => y[p1][p3]==1;
y[p1][p2]+ y[p2][p3] -1<= y[p1][p3]; // linear

regards

Yes this was a mistake, you re right!