(* Assign.m
 * A Mathematica program for assigning papers to a committee
 * of reviewers.
 *
 * by Peter Lee (petel@cs.cmu.edu), July 1994
 * with help from Dana Scott on the use of Mathematica
 * and John Mount (and indirectly Mike Trick) on linear programming.
 * (John/Mike gave me all of the right constraints to use.)
 *
 * This program was written to aid in assigning submitted papers to the
 * POPL95 program committee.  It should be useful for many standard
 * conference program committees, though it requires some information
 * from the members of the program committees (henceforth called the
 * "reviewers").
 *
 * DATA FILES
 *
 * This program reads a collection of data files.  These files describe
 * the papers to review, as well as the expertise of the reviewers.
 * More specifically:
 *
 *   - A "papers" file contains a listing of the topic(s) of each paper.
 *   - A "reviewers" directory contains one file from each reviewer,
 *     each file listing the "expertise" of the reviewer in each topic.
 *
 * All of the data is given as integers.  For the "papers" file, the
 * papers are numbered and arbitrary values encode the topics.  For
 * example, here is a small sample "papers" file, describing 3 papers:
 *
 *     1 14
 *     2 9 28 15
 *     3 32
 *
 * This file describes 3 papers, the first being on topic 14, the second
 * on topics 9, 28, and 15, and the third on topic 32.  There is no limit
 * on the number of topics per paper, though there must be at least one.
 *
 * A reviewer file gives a reviewer's competence rating on each topic.
 * For example, here is a small excerpt of a reviewer file called "lee":
 *
 *    1 2
 *    2 0
 *    3 0
 *    4 3
 *    ...
 *
 * This specifies that reviewer "lee" has competence 2 on topic 1,
 * competence 0 on topics 2 and 3, competence 3 on topic 4, etc.  Note
 * that you can supply your own "cost function" (described below), but
 * if you want to use the default cost function, then competence ratings
 * should be on a 0 to 3 scale, where 0 means "I've never heard of that
 * topic before" and 3 means "I'm an expert on that topic".  Note also
 * that a missing competence rating is interpreted as 0.
 * RUNNING THE PROGRAM
 *
 * Once these files are in place, this program is easy to load and
 * run.  First, start Mathematica, and load this package:
 *
 *	<<assign.m
 *
 * Then, simply call the Init function, giving the name of the "papers"
 * file and the "reviewers" directory as arguments.  Then, call assign
 * with the number of times each paper should be reviewed.  For example:
 *
 *	Init ["papers", "reviewers"]
 *	Assign [3,20]
 *
 * This specifies that the papers described in file called "papers"
 * are to be assigned to the reviewers described in the directory
 * "reviewers", with each paper getting 3 reviews.  The second argument
 * to Assign is an assignment bound; here, between Floor[(10/11)kP/R] and
 * Ceiling[(11/10)kP/R] papers will be assigned to each reviewer (where k
 * is the number reviews per paper (=3 in this example), P is the number
 * of papers, and R is the number of reviewers).  Making this argument be
 * a high number (like 100) evens out the distribution of papers amongst
 * the committee members, but could result in poor assignments, so you'll
 * probably want to play around with this number and allow some unevenness
 * in the number of papers assigned to each reviewer.
 *
 * If you have a large-ish conference (say, more than 200 papers and 15
 * reviewers), then you should be prepared to wait a few hours.  I wrote
 * this more for clarity than speed.  If speed is a problem, then it will
 * be extremely useful to split the "papers" file into several small pieces.
 *
 *
 * COST FUNCTIONS
 *
 * This program is simple because it uses the built-in linear-programming
 * features of Mathematica.  This means, of course, that the cost function
 * that measures the "goodness" of an assignment of papers must be linear.
 * This is quite a severe limitation, but at least this leads to fairly
 * predictable results (and for a large conference is certainly better
 * than what I can do by hand in a reasonable amount of time).
 *
 * The default cost function is essentially as follows:
 *
 *	sum over all r in reviewers.
 *	  sum over all p in papers.
 *	    r[p] * Cost[r,p]
 *
 * where r[p]==1 if reviewer r is assigned paper p and 0 otherwise.
 * The function Cost thus calculates the cost of assigning paper p to
 * reviewer r.  (High costs are bad, 0 is best.)  The default Cost
 * function is in the public part of this package, so you are free to
 * define your own.  But the overall cost function must be linear.
 *)
BeginPackage["Assign`"]

Assign::usage =
	"Assign[reviewsPerPaper] assigns papers to the reviewers
	so that each paper gets exactly reviewsPerPaper reviews."

Init::usage =
	"Init[papersFile,reviewerDirectory] initializes this
	paper-assignment package by reading the paper topics
	and reviewer competence ratings."

Cost::usage =
	"Cost[reviewer,paper] calculates the cost of assigning
	the paper to the reviewer.  Replace this function with your
	own if desired."


Begin["`Private`"]

(* Global variables private to this package:
 *
 *	topics: an association list binding paper numbers to topics
 *      papers: the list of papers
 *	numPapers: the number of papers
 *	reviewers: a list of strings giving the names of the reviewers
 *		   (this list obtained from the file names in the
 *		    reviewers directory)
 *	ratings: an association list binding each reviewer name to an
 *		 an association list binding topics to competence scores.
 *)

(*
 * The default function Cost, for calculating the cost of assigning
 * a paper to a reviewer.
 *)
Cost[reviewer_, paper_] :=

 (* First, retrieve the topics of the paper and the ratings given
  * by the reviewer. *)
 With[
  {paperTopics = Rest[First[Select[topics, First[#] == paper &]]],
   ratingData  = Part[First[Select[ratings, First[#] == reviewer &]], 2]
  },

  (* Then, extract the competence scores, given the topics. *)
  With[
   {scores =
      Map[Function[topic,
	    With[{ratings = Select[ratingData, First[#] == topic &]},
	         If[ratings=={}, 0, Part[First[ratings],2]]]],
	  paperTopics]
   },

   (* Finally, convert the average competence score into an assignment cost,
    * using a sliding scale. *)
   Switch[Round[Fold[Function[{s,n},s+n],0,scores] / Length[scores]],
          0, 100,
          1, 90,
          2, 75,
          3, 25,
          4, 0]
 ]];
(*
 * The paper-assigning function.
 *)
MakeAssignment[minRead_, maxRead_, reviewsPerPaper_] :=
(
 (*
  * Set up the constraints.
  *)
 Print["    building constraints..."];
 (* Constrain each element of the assignment matrix to be either 0 or 1.
  *
  *	forall r in reviewers.
  *	  forall p in papers.
  *	    0 <= r[p] <= 1
  *
  * where r[p]==1 if reviewer r is assigned to read paper p, else 0
  *)
 AssignmentMatrix =
   Flatten[Map[Function[r, Map[Function[p, r[p] <= 1], papers]], reviewers]];

 (* Constrain each element of the totals vector to lie in the range
  * minRead..maxRead.
  *
  *	forall r in reviewers.
  *	  minRead <= num[r] <= maxRead
  *
  * where num[r] is the number of papers assigned to reviewer r.
  *)
 TotalsVector =
   Map[Function[r, minRead <= num[r] <= maxRead], reviewers];

 (* Constrain the assignment matrix so that each paper is read enough times.
  *
  *	forall p in papers.
  *	  (sum over all r in reviewers. r[p]) == reviewsPerPaper
  *)
 ReviewsPerPaperConstraints =
   Map[Function[p,Fold[Function[{s,r},s+r[p]],0,reviewers] == reviewsPerPaper],
       papers];

 (* Constrain the totals vector for the proper values.
  *
  *	forall r in reviewers.
  *	  (sum over all p in papers. r[p]) == num[r]
  *)
 ReviewsPerReviewerConstraints =
   Map[Function[r, Fold[Function[{s,p},s+r[p]],0,papers] == num[r]],
       reviewers];

 (* Finally, a constraint to ensure that we have the right number of reviews.
  *
  *	(sum over all r in reviewers. num[r]) == reviewersPerPaper * numPapers
  *)
 TotalReviewsConstraint =
   Fold[Function[{s,r}, s+num[r]], 0, reviewers] == reviewsPerPaper*numPapers;
(*
 * The linear cost function.
 *
 *	sum over all r in reviewers.
 *	  sum over all p in papers.
 *	    r[p] * Cost[r,p]
 *
 *)
 Print["    building cost function..."];
 CostFunction =
   Fold[Function[{s,r},
          s + Fold[Function[{t,p},t+r[p]*Cost[r,p]],0,papers]], 0, reviewers];


 (* Finally, we use Mathematica's built-in linear-programming feature
  * to solve the constraint problem.
  *)
 Print["    performing global minimization..."];
 MinCost = Timing[
   ConstrainedMin[
     CostFunction,

     Append[Join[AssignmentMatrix,
                 TotalsVector,
                 ReviewsPerPaperConstraints,
                 ReviewsPerReviewerConstraints],
            TotalReviewsConstraint],

     Join[Map[Function[r, num[r]], reviewers],
          Flatten[Map[Function[r, Map[Function[p, r[p]], papers]],
                      reviewers]]]]]
) (* end of MakeAssignment function *)


(*
 * The Assign function.
 *)
Assign[ReviewersPerPaper_,Bound_] :=
 With[
  {minRead =
     Floor[(Bound/(Bound+1)) ReviewersPerPaper numPapers / Length[reviewers]],
   maxRead =
     Ceiling[((Bound+1)/Bound) ReviewersPerPaper numPapers / Length[reviewers]]
  },

  (Print["Working on a solution with ",minRead," to ",maxRead,
         " papers per reviewer..."];
   Solution = MakeAssignment[minRead, maxRead, ReviewersPerPaper];
   Print["    done.  CPU time used: ", Part[Solution,1]];
   PrintSolution[Part[Solution,2]];
   Print["Assignment completed."]
  )
 ]
(*
 * Printing function for solutions to the constraint system.
 *)
PrintSolution[Solution_] :=
 (Print[" "]; Print ["Total cost: ", First[Solution]];

  WorstCost =   (* Calculate the cost of the worst-loaded reviewer. *)
    Max[Map[Function[r,    (* ...calculate the worst-loaded reviewer. *)
              Fold[Function[{s,p},
                     s+If[(r[p]/.Part[Solution, 2])==1,Cost[r,p],0]],
                   0, papers]],
            reviewers]];
  Print["Worst cost: ",WorstCost];

  A = Part[Solution, 2];   (* Extract the paper assignments *)

  Map[Function[r,(Print[r," assigned ",num[r]/.A," papers:"];
		  Print["	",
		        Fold[Function[{z,p},If[(r[p]/.A)==1,Append[z,p],z]],
		             {}, papers]])],
      reviewers];
  Print["----------"];
  Map[Function[p,(Print[p," -> ",
                        Fold[Function[{z,r},If[(r[p]/.A)==1,Append[z,r],z]],
                             {}, reviewers]])],
      papers]
 )



(*
 * The initialization function.
 *)
Init[topicsFile_, reviewerDir_] :=
 With[
  {files =                       (* Get names of competence files *)
     FileNames["*", {reviewerDir}]
  },

 (
  (*
   * Read in all of the competence files.
   *)
  reviewers =                   (* Extract reviewer names from file names *)
    Map[Function[x, StringReplace[x, {reviewerDir<>"/" -> ""}]], files];

  ratings =                     (* Read the competence ratings *)
    Thread[Function[{reviewer,data},{reviewer,data}]
           [reviewers,
            Map[Function[f, ReadList[f, Number, RecordLists->True]], files]]];

  (*
   * Read in file containing the topics of each paper.
   *)
  topics = ReadList[topicsFile, Number, RecordLists->True];
  papers = Map[Function[t, t[[1]]], topics];
  numPapers = Length[papers];

  Print["Initialization complete."]
 )]

End[ ] (* private part *)
EndPackage[ ]
