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