classroom combinatorics
in [Mathematica]
|
From: McGill, Paul on 1 Aug 2010 04:56 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
From: Daniel Lichtblau on 5 Aug 2010 07:01 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
From: telefunkenvf14 on 6 Aug 2010 06:58 On Aug 5, 6:01 am, Daniel Lichtblau <d...(a)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
From: Daniel Lichtblau on 6 Aug 2010 06:58 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
From: Chris Pemberton on 7 Aug 2010 01:31 On 08/06/2010 05:58 AM, Daniel Lichtblau wrote: > 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 > This is a classic example of the "social golfer problem" which has been giving mathematicians heartburn for years. From what I've read, event organizers usually resort to using pre-printed tables to do the pairings .... but it looks like someone as been kind enough to provide a Mathematica demonstration: http://demonstrations.wolfram.com/SocialGolferProblem/ This explains why you never want to go golfing with a large group of mathematicians. Chris
|
Pages: 1 Prev: graphics3d listanimate Next: MinCut crashes the Mathematica kernel |