Re: classroom combinatorics
- To: mathgroup at smc.vnet.net
- Subject: [mg111589] Re: classroom combinatorics
- From: telefunkenvf14 <rgorka at gmail.com>
- Date: Fri, 6 Aug 2010 06:58:23 -0400 (EDT)
- References: <i3e5mb$hgv$1@smc.vnet.net>
On Aug 5, 6:01 am, Daniel Lichtblau <d... at wolfram.com> 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 group s > > 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 1. I stumbled on that Knapsack paper earlier this summer. Fun examples---made my laptop HOT!!! 2. Daniel: Your clarity of thought is disgusting. (And I mean that in a nice/respectful/envious kind of way.) -RG