Math 100A Teaching Assignment

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 100A teaching
assignments.

The problem has been formulated in a general matrix form. We must decide
our parameters.

Clear[m,n,l,rs,cs,overlaps,d,y,obj, ystar, R, C, conj,
 conjunc]

m = 7;   (* number of TAs *)
n = 4;   (* number of classes *)
l = 0;   (* number of overlap times *)

Overlap Matrix

One of the first things that must be considered in this problem is when
classes overlap.  For example, if a person is teaching Caluclus recitation
at 9:30 AM on Tuesday and Thursday, then that same person will not be
available to teach trigonometry at 9:30 AM on Tuesday and Thurdays.  In
order to address this problem, we can create overlap vectors.    Each class
time which has more than one class scheduled during it will have an overlap
vector.  The notation for the vectors is as follows:  a 1 represent a class
to be held at that time and a 0 represents no class.

In this particular problem, there are no overlap times among the sections
of 100A. Consequently, we do not have to construct overlap vectors.

Row Sum Matrix

We must check that each TA is given the proper number of assignments.   To
do this, we will consider the row sums of the assignment matrix.   Recall
that  the row sum matrix will be a matrix that rotates an n vector of ones
across the rows.

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

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

MatrixForm[R]

Dimensions[R]

Column Sum Matrix

We must also be sure that each class has a teacher.  In this case we will
consider the column sums.   The column sum matrix is simply m nXn
identity matrices stacked next to each other.

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

MatrixForm[Cs]

Dimensions[Cs]

Constraint Matrix

Our complete constraint matrix will contain the overlap matrix, the row
sums, the column sums, and a atrix to insure that the solutions will be in
the unit interval.

However, in this case, since we do not have any overlap vecotrs in this
problem, we will omit the overlap matrix from the constraint  matrix.

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

MatrixForm[A]

Dimensions[A]

Right Hand Side

If we had an overlap matrix, we would have to include a right hand side
vector corresponding to the overlap matrix.  However, in this case we don't
have one.  Thus, we must only consider the row sum and column sum
constraints.

The values for the row sums and column sums  are predetermined by the
department.  Recall that these are the values for the required number
assignments for each GTA (row sums) and for each class (column sums).

rs = {1,1,1,1,1,1,1}

cs = {2,2,1,2}

We will aggregate all of the contraint requirements into the
right-hand-side vector b.

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

Dimensions[b]

Objective Function Coefficients

The values for these coefficients will be determined by the GTAs' class
schedules  as well as preferences.  This vector represents when GTAs are
and are not available.

d = {0,-10000000,0,0,
        0,0,0,0,
        0,0,-10000000,0,
        0,0,0,0,
        0,0,-10000000,0,
        0,-10000000,-10000000,0,
        0,0,0,0}

Dimensions[d]

A Possible Solution

Note that LinearProgramming solves for min cx  subject to Ax >= b where x>=
0.  Our problem is of the form max cx subject to Ax <= b, x >= 0.  Since we
wish to maximize cx, we consider -c.  Also,  in order to accomodate for the
equality constraints, we must also consider -RSx < =  -rs, and -CSx <= -cs.
Finally,  since our inequlities are exactly opposite of the form needed
for the LinearProgramming command, we simply multiply everything by a
negative one.

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

It took Mathematica under  7 seconds to find this solutoin.

obj = d.Last[ystar]

Having an objective function value of zero indicates that there wre no
prohibited assignments made.

The solution vector can be formatted back into matrix from so that it is
easier to evaluate.  The rows of the following matrix represent the
different GTAs and the columns represent the different classes.

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

>From the solution matrix, we see that GTA 1 is assigned to class 3, GTAs 2 and 3 to class 2, GTAs 4 and 5 to class 1, and GTAs 6 and 7 to class 4.

Conjunction Vectors

Note.  This material was not discussed in Ms. Yen's paper; it represents
one direction in which Professor Dunbar worked on extending her basic
results.  [Ed.]

Suppose that we wanted to test for joint assignment.s.  In this case, we
would use our conjunction vectors.  Suppose that the person assigned to
teach class 1 also needs to be assigned to teach class 2.  Then we would
have following conjunction vector:

conjunc = {{{1,1,0,0}}}

We will need to normalize this vector.  We will use the following functions:

normalize[vector_List] := vector/Apply[Plus, vector]

makeconjun[threelevellist_List] :=
        Map[ normalize, Flatten[threelevellist,1]]

Our normalized conjunction vector becomes

conj = makeconjun[conjunc]

T = Transpose[conj]

MatrixForm[Partition[Last[ystar],n].T]

>From this matrix, we deduce that GTAs 1, 6, and 7 satisfy the conjunction
constraint.  The zero balue indicates that GTAs 1, 6, and 7 are assigned to
neither class 1 nor class 2.  As for the other GTAs, the 1/2 indicates that
each of them is assigned to one class but not the other.
^*)