Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: classroom combinatorics

  • To: mathgroup at smc.vnet.net
  • Subject: [mg111592] Re: classroom combinatorics
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Fri, 6 Aug 2010 06:58:56 -0400 (EDT)

Daniel Lichtblau wrote:
> McGill, Paul wrote:
>> My wife, who is a business professor, asked me an interesting question 
>> today. She has 28 students in her class and wants them to meet in groups 
>> four, once each class session, such that every student gets at least one 
>> chance to work with every other student in a minimum number of class 
>> sessions. For instance, if the class had only nine students and met in 
>> groups of three, you could accomplish this in four class sessions:
>>
>>
>> c1 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
>> c2 = {{1, 4, 7}, {2, 5, 8}, {3, 6, 9}}
>> c3 = {{1, 5, 9}, {2, 6, 7}, {3, 4, 8}}
>> c4 = {{1, 6, 8}, {2, 4, 9}, {3, 5, 7}}
>>
>> How can I use Mathematica to figure this out? I've looked through the 
>> tutorial for the Combinitorica package and see nothing quite like this 
>> case. Can anyone give me a nudge in the right direction?
>>
>> Thanks,
>> Paul
> 
> I do not know of a convenient way to go about this. There may well be 
> something, it's just not an area with which I am familiar.
> 
> In principle it can be set up as a constraint satisfaction problem in 
> integer linear programming. We assume there is some fixed number of 
> sessions. To minimize that you would simply bring down the number of 
> sessions until you no longer can satisfy the constraints.
> 
> There will be one variable for each session and pair of students. All 
> variables will be 0 or 1. If 1, that pair is meeting in that session, 
> else not. This imposes already two classes of constraint: that all 
> variables are between 0 and 1 inclusive, and that they are all integer 
> valued.
> 
> The other constraints will be:
> 
> Sum over a round of student j  with all students k is equal to group size.
> 
> Sum over all sessions of student j with student k is >= 1.
> 
> Compatibility: if student j meets with k in session i, and k meets with 
> l in same, then must have i meeting with l in same session. We impose 
> this as an inequality: r[i,j,k] >= r[i,j,l]+r[i,k,l] - 1, where i is the 
> session number and the trio of students is {j,k,l}. We permute so that 
> we actually have three such constraints for this trio.
> 
> Here is code that can set this up. I use the smaller size problem.
> 
> rounds = 4;
> n = 9;
> size = 3;
> 
> vars = Array[r, {rounds,n,n}];
> vars = vars /. r[i_,j_,j_]:>Sequence[];
> vars = vars /. r[i_,j_,k_]/;j<k :> r[i,k,j];
> fvars =  Union[Flatten[vars]];
> 
> c1 = Map[Total[#]==size-1&, vars, {2}];
> c2 = Map[Total[#]>=1&, Transpose[vars,{3,1,2}], {2}];
> c3 = Map[0<=#<=1&, fvars];
> c4 = {Element[fvars,Integers]};
> c5 = Table[r[i,j,k]-(r[i,j,l]+r[i,k,l])>=-1,
>    {i,rounds}, {j,2,n}, {k,1,j-1}, {l,n}] /.
>      r[i_,j_,j_]:>Sequence[] /.
> 	r[i_,j_,k_]/;j<k :> r[i,k,j] /. True:>Sequence[];
> 
> constraints = Union[Flatten[Join[c1,c2,c3,c4,c5]]];
> 
> Timing[inst = FindInstance[constraints,fvars]]
> 
> The problem with this simple setup is that it is in no hurry to 
> complete. You might gain a bit of advantage by fixing the first session, 
> e.g. enforcing that the students split into groups of consecutive 
> threesomes, as in your solution (any such split is fine for the first 
> session). I do not know how much this will help.
> 
> You could also replace FindInstance, which uses exact linear programming 
> under the hood, with e.g. an interior point method. This would involve 
> writing your own branching loop instead of just calling FindInstance. 
> For some approaches to this, have a look at notebooks at URL below.
> 
> http://library.wolfram.com/infocenter/Conferences/7515/
> 
> Another idea is to enforce the compatibility constraints incrementally, 
> starting with none and only adding (some of) those that the prior 
> solution has violated. This might work faster in that FindInstance can 
> handle the problem when the compatibility constraints are not present; 
> problem is, the solution it gives will violate some of them.
> 
> These tactics might make the problem closer to tractable, though I doubt 
> it will handle anything of significant size.
> 
> Daniel Lichtblau
> Wolfram Research

Follow-up: It took around 3.5 hours to get a result using the code above.

I keep forgetting FindMinimum has an interface to some fast integer 
linear programming. It uses an interior point method, with machine 
precision for handling the relaxed linear programming problems; this 
means it can give incorrect results in extreme situations. But it is 
certainly worth trying out for a problem like this. Below shows how one 
might use it for this example; set-up is as before.

In[69]:= Timing[{min,inst2} = FindMinimum[{1,constraints}, fvars];]
Out[69]= {3.62345, Null}

In[70]:= InputForm[vars/.inst2]
Out[70]//InputForm=
{{{0, 0, 0, 0, 0, 0, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 0},
   {0, 0, 0, 1, 1, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 0, 0},
   {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0},
   {0, 1, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 1},
   {1, 0, 0, 0, 0, 0, 0, 1}}, {{0, 1, 1, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 1, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 0, 0},
   {1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 0},
   {0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 1, 0, 1, 0},
   {0, 0, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 0, 1, 0, 0}},
  {{0, 0, 0, 0, 1, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0},
   {0, 1, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 1, 0, 0},
   {1, 0, 0, 0, 0, 1, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0},
   {0, 0, 0, 1, 1, 0, 0, 0}}, {{1, 0, 0, 1, 0, 0, 0, 0},
   {1, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 1},
   {0, 0, 0, 0, 1, 0, 1, 0}, {1, 1, 0, 0, 0, 0, 0, 0},
   {0, 0, 0, 1, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 1},
   {0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 1, 0}}}

Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: classroom combinatorics
  • Next by Date: Rearrange equation II
  • Previous by thread: Re: classroom combinatorics
  • Next by thread: Re: classroom combinatorics