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

**Re: classroom combinatorics**

**Rearrange equation II**

**Re: classroom combinatorics**

**Re: classroom combinatorics**