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