Math 102 Teaching Assignments

From the article by Joyce Yen in
Mathematica in Education and Research
Vol.4 No.4

Copyright 1996 TELOS/Springer-Verlag

Background information

This notebook will produce a possible solution for Math 102 teaching
assignments.

Clear[m,n,k,rs,cs,overlaps,R, Cs,V,d, y, con, conjunc,
ystar,obj]

m = 4;   (* number of TAs *)
n = 6;   (* number of classes *)
l = 4;   (* number of overlap times *)
cj = 2;  (*number of conjunction vectors*)

Overlap Matrix

We will need some computer programming  to construct the overlap matrix.
We wish to rotate the overlap vector through the matrix so that each GTA's
assignments can be checked.  To do this, we will need the following
functions.

nzeros = Table[0, {i,1, n}];

buildOverlap[overlapvector_] :=
NestList[
        RotateRight[#,n]&,
                Join[
                        overlapvector,
                        Flatten[
                                Table[
                                        nzeros,
                                        {i,1,m-1}
                                ]
                        ]
                ],
                m-1
]

overlaps = {{0,1,0,0,1,0},{0,1,0,0,0,1},
     {0,0,0,0,1,1},{0,0,1,0,0,1}}

V = Flatten[ Map[buildOverlap, overlaps], 1];

Dimensions[V]

Conjunction Vectors

Note.  Conjunction vectors were not discussed in Ms. Yen's paper; they
represent one direction in which Professor Dunbar has worked on extending
her basic results.  [Ed.]

Suppose that we wanted to test for joint assignments.  In this case, we
would use our conjunction vectors.  Accroding to the schedule of classes
for Spring 1995, sections 201 and 202 of Math 102 are held sequentially on
East Campus.  It would be best to have the same person assigned to teach
both sections.  In this problem these two sections are represented by class
hours 5 and 6, respectively.  The idea is to have -x5 + x6 <= 0  and x5 -
x6 <= 0.  We can change this information into vector notation.  To check
whether these two teaching assignments are made in conjunction, we would
form  following conjunction vector:

conj = {{0,0,0,0,-1,1},{0,0,0,0,1,-1}}

J = Flatten[ Map[buildOverlap, conj], 1];

Dimensions[J]

Row Sum Matrix

We will need to consider how many class-hours each GTA must teach.  We can
represent this information with row sums.

row1 = Table[ If[i <= n, 1,0], {i,m*n}]

R = NestList[
        RotateRight[#,n]&,
                row1,
                m-1
];

Dimensions[R]

Column Sum Matrix

Cs = Transpose[Flatten[ Table[IdentityMatrix[n],
{i,1,m}],1]];

Dimensions[Cs]

Constraint Matrix

A = Join[V, J, R,-R,Cs,-Cs, IdentityMatrix[m*n]];

Dimensions[A]

Ignoring the conjunction vectors,

A1 = Join[V, R,-R,Cs,-Cs, IdentityMatrix[m*n]];

Right Hand Side

v = Table[1,{i,1,m*l}]

j = Table[0,{i,1,m*cj}]

r = {2,2,3,3}

cs = {1,2,2,3,1,1}

b = Join[v,j,r,-r,cs,-cs,Table[1,{i,1,m*n}]]

Dimensions[b]

b1 = Join[v, r,-r,cs,-cs,Table[1,{i,1,m*n}]]

Objective Function Coefficients

d = {0,-1,0,0,0,0,
        0,0,0,0,0,0,
        0,0,0,0,0,0,
        0,0,0,0,0,0}

Dimensions[d]

Not e that even if there are no conflicts with any of the TAs, the list of
objective function constraints cannot be all zeros.  If it is, the
LinearProgramming command will say that part 2 does not exist.

A Possible Solution

ystar = LinearProgramming[-d,-A,-b]//Timing

This solution took Mathematica just over 7 seconds to find a solution.

obj = d.Last[ystar]

y = MatrixForm[Partition[Last[ystar],n]]

A Solution Disregarding the Conjunction Vectors.

ystar1 = LinearProgramming[-d,-A1,-b1]//Timing

obj1 = d.Last[ystar1]

y1 = MatrixForm[Partition[Last[ystar1],n]]