czlee / adjumo

Allocating Debate Judges Using Mathematical Optimization

Adjumo

Allocating Debate Judges Using Mathematical Optimization

General information

• A demo of the interface (excluding the allocations solver) is available here.
• A report describing challenges involved in using the system at WUDC 2016 is available here.

Getting started

Julia & Julia Packages

You need to install Julia, and then install a bunch of Julia packages. Julia downloads are at http://julialang.org/downloads/. Download and install the latest stable version, which is currently 0.4.2.

To install the required packages, run:

julia julia/installrequirements.jl [gurobi] [cbc] [glpk] [psql]

If you're not familiar with optimisation solvers, read the below material on the solver libraries first!

With no arguments, it will install CBC.jl and GLPKMathProgInterface.jl, but not Gurobi.jl or PostgresQL.jl. If any solver (gurobi, cbc, glpk) is specified, it will install only those specified. It will only install PostgreSQL.jl if psql is specified. The order of arguments does not matter.

To see what this installs, inspect installrequirements.jl (it's a simple enough file).

Solvers

There are three options: Gurobi, CBC and GLPK. You only need one of them.

Option 1: Gurobi. Gurobi is a commercial optimization solver. You need a license to use it. If you can get hold of a Gurobi license:

Pkg.add("Gurobi")

Note: This will fail if you don't have Gurobi installed.

If you want to use Gurobi Cloud, you need a fork of this repository, since the official one doesn't yet support Gurobi Cloud:

Pkg.clone("https://github.com/czlee/Gurobi.jl.git")

If you can't get a Gurobi license, then we can use one of the open-source solvers, CBC or GLPK.

Option 2: CBC. To install CBC:

Pkg.add("Cbc")

This will take a while and you'll see lots of gibberish printed on the screen. You need a C compiler, a C++ compiler and Make installed in order to build CBC. If you get error messages complaining about the lack of any of them, exit Julia and run these from the shell:

sudo apt-get install gcc
sudo apt-get install g++
sudo apt-get install make

Then try again.

Option 3: GLPK. To install GLPK, first install the libgmp-dev package, from the shell (outside Julia):

sudo apt-get install libgmp-dev

Then install in Julia:

Pkg.add("GLPKMathProgInterface")

User Interface

Dependencies

• Node.js
• Bower

Frontend Setup

• cd frontend
• npm install
• bower install
• ember serve --proxy http://0.0.0.0:3000 (open http://localhost:4200/ to confirm it's working)

Note: the front end requires that there are json files present in public/data to be imported

Backend Setup

• cd backend
• npm install
• npm start (open http://0.0.0.0:3000/ to confirm it's working)

Usage

• To start the server: ember serve --proxy http://0.0.0.0:3000 --environment="production" --live-reload false
• Open http://localhost:4200

Running

Julia part only

The file that runs the allocations the Julia part is called allocate.jl and can be run directly from the shell:

julia allocate.jl

This generates random data for a pretend round and runs the algorithm on it. You can run it with a different number of debates, or pretend the current round is something else. For example, to run it with a round comprising 10 debates, pretending it is currently round 3:

julia allocate.jl -n 10 -r 3

If you installed more than one of the solvers above, you can choose which one to use with --solver. For example, to use GLPK:

julia allocate.jl --solver glpk

The other options are cbc and gurobi. If you don't specify, it'll try Gurobi, then CBC if Gurobi isn't installed, then GLPK if neither of the other two are installed.

For more options:

julia allocate.jl --help

Documentation

Requires ruby, and running:

  gem install github-pages

Then check out the gh-pages branch and run:

  jekyll s

adjumo's Issues

Disallow dragging adjudicators between multiple allocations

We never ended up using the iterative allocations options, but if it ever was the front end should block particular adjudicator objects from being dragged between different allocation iterations.

Front-end prototype

Just a quick explainer on how the current prototype works:

• index.html is served, and uses jquery to parses JSON from a particular end point
• This endpoint is routed using Express in routes/index.js
• The second router.get is a dummy for importing the JSON file from Tabbie 2 (currently used dummy.json)
• This then gets passed back to index.html as JSON to render each room onto the table
• After each room/table row is rendered a call is made to another end point, passing it on a dummy importance value
• This is handled by the third router.get in routes/index.js, which passes this dummy importance value to a function inside a julia script and then returns the result as JSON
• This JSON is parsed and rendered into the table as the dummy importance value

I'm documenting this as a rough prototype of the architecture and to demonstrate it's viability. Currently its setup as a completely separate front & backend and we will probably need model layers on both. I'm pretty confident I can get the front end going as needed.

The larger question is more the backend and whether we want to keep it running in node.js or use django calling into Julia as you suggest. This is partly a question of speed and partly a question of what you would be most comfortable working with. Quick thoughts:

• Maybe we should try the python calling into julia option and benchmark it to see how fast it is
• Most of the backend work will be creating end points for getting/putting data from the database, so it should be relatively simple regardless of language/framework.

See if solver can be stopped prematurely

JSON exports need root level data element to conform to JSON API

Ember Data expects the JSON to confirm to the API's top level requirements notably the need for a root data element.

Instead of:

[
  {
    "attributes": {
      "name": "Molepolole 1",
      "gender": 3,
      "id": 89727,
      "language": 1,
      "region": 5
    },

It should be:

{
  "data": [
  {
    "attributes": {
      "name": "Molepolole 1",
      "gender": 3,
      "id": 89727,
      "language": 1,
      "region": 5
    },

I had a brief look at modifying the Julia to do so, but would probably actually need the language to do so. Not urgent (I've modified my own files to work as specified).

PS: In d6b9a81 I've changed the filepath for testjson.jl exports so its clear where ember is loading them from.

Julia's JSON exports should create a regions.json

Low-priority (I've committed a regions.json file to the repo and it's not like its going to be changing very often)

Add demo site using github pages

So in theory the front-end should be able to run independently on github docs. I've ported over the compiled version of the site there, and added in some random data sets I had around. It will then live over at http://czlee.github.io/adjumo/

It would be great if you could go ahead and drop into the data file a more complex data set, and also a debate-importances.json and a panel-allocations.json so that an allocation will load — my julia and/or node installs are a little rekt rn. We probably also want to have some intro at some point explaining the basics (Set Parameters wont actually work; you have to hit Load Allocation to see stuff etc).

Small changes to Julia types & JSON exporting

First of which is that I was working under the assumption that Adjudicators should be able to have multiple institutions for the purposes of regional diversity and/or conflict highlighting. So the expected JSON API output would be:

"relationships": { "institutions": { "data": [ {"id":2345,"type":"institution"} ] } }

I can see where this would be changed in types.jl but I assume that will mess up a bunch of other things. Not urgent as I can just manually edit the JSON to conform for now.

Convert print statements to logging

I underestimated the extent to which users (or at least I) would need to rely on the console output of allocate.jl to track what was going on, and to keep a record of what was happening. The code currently includes a ton of println statements to report on various things at various times. Some of these things are inevitable, for example, the printout from Gurobi/CBC/GLPK doesn't come from Adjumo (unless Adjumo wants to intercept it). But there are enough println statements that a more organised system for managing them is probably in order.

It might therefore be useful to migrate to a basic logging system with levels, hierarchies, and with inbuilt support for logging to files.

There is a Python-inspired package here: https://github.com/kmsquire/Logging.jl

Eventually:

• If/when running the allocator directly from the UI is implemented, we'd want to pipe the logs to the user in real time. It's not intuitive to the layperson, but realistically, Adjumo users will have to be trained to at least some degree for other reasons. The output could show when a link is clicked, like the build logs in Heroku.
• All logs should be saved to a file, by default. An essential part of running a tournament is being able to revisit what happened earlier on. Nothing should ever overwrite anything without archiving it somewhere. (This is possibly a different issue, but it holds, inter alia, for log files.)

Tabbie2 should export and Adjumo should import both adjudicator society and user societies

I think the following:

• Adjudicator's society is just for this tournament
• User's societies are eternal and used for clashes

Both should be used for clashes, at least for WUDC 2015

Add solver progress tracking and best solutions

See https://jump.readthedocs.org/en/latest/callbacks.html#querying-solver-progress

MathProgBase.cbgetmipsolution is probably useful:
http://mathprogbasejl.readthedocs.org/en/latest/lpqcqp.html#cbgetmipsolution

Note: this requires the use of GLPK or Gurobi, not CBC, as CBC doesn't support MIP callbacks (I think).

See if solver can return multiple solutions

Low priority, wait for @philipbelesky to do interface mock-up and assess usefulness.

Team-adjudicator conflicts

It's not really clear how best to deal with team-adjudicator conflicts. It'll require investigation, probably closer to the time when we have more realistic data sets. Perhaps it could be made an option. Thoughts:

• There's no exhaustive list of team-adjudicator conflicts. The list on RoundInfo is only "custom" ones; institution clashes are just checked directly in the code.
• Adding team-adjudicator conflicts to the constraints of the model for the solver might be intensive, and this takes time.
• This is especially the case if we want to add institution clashes—there is no easy way to look up "all teams from an institution" with the current data structure.
• However, lazy constraints might offer a way to alleviate this.
• On the other hand, adding team-adjudicator conflicts might reduce the search space of the problem, which might make it faster to solve.

Incompatible constraints

It would be nice if, when the solver thinks the problem is infeasible, we could tell the user why. The solver doesn't know, at least not in human terms, so we'd have to check this ourselves. If the problem is infeasible, it means there are some constraints that are incompatible with each other. A naïve approach would be to run through all the incompatible conditions we can think of, checking for each of them. I don't have any ideas for less naïve approaches.

The constraints permitted by the system are:

• Adjudicator-adjudicator conflicts
• Team-adjudicators conflicts
• Locked adjudicators
• Blocked adjudicators
• Grouped adjudicators

Here is an incomplete list of ways in which constraints can be incompatible:

• Adjudicators that are conflicted are also grouped.
• An adjudicator is locked to a debate containing a team with which he conflicts.
• An adjudicator is locked to a debate from which she is also blocked.
• Adjudicators that are grouped are also locked to different debates.
• A group of adjudicators contains one that is locked to one debate, and one that is blocked from another.
• An adjudicator that conflicts with a team, is grouped with an adjudicator who is in turn locked to a debate containing that team.
• Two adjudicators are locked to the same debate, but conflict with each other.

Julia performance benchmarks

This is a list of things that should be profiled to check which way runs better.

• Use sparse matrices for the membership matrix, rather than full matrices.
• Store the adjudicator indices with AdjudicatorPanel (rather than using findfirst).
• Parallelize score matrix generation.
• Define a custom iterator interface for AdjudicatorPanel (or two: one with c/p/t info, one without)
• Rewrite sumadjadjscoresvector using matrix multiplication, like sumteamadjscoresmatrix

Trainee allocations

1. Model the idea that trainees might not be allocated as panellists. This requires an unallocated trainee to have a score that is higher than their being allocated, all things being equal.
2. Provide scope for unallocated trainee information to be retained.
3. Write the part that allocates trainees after all panels are locked in.

Debate weights calculator

Includes deficits.

Recalculating debate-panel scores

The function that does this is score() in score.jl. But it currently takes (::RoundInfo, ::Debate, ::AdjudicatorPanel), which isn't great for a Node.js call. Also, it only returns one number -- the end result -- when really it should return every component (the front end doesn't have to use all of them).

I assume you'd like it to return a JSON file with all of the scores. This might (as a suggestion) look something like this:

{"quality": {"weight": 1.4, "score": 24.5}, "regional": {"weight": 1, "score" -23.0}, ...}

where "weights" refer to component weights. If you don't want component weights then it can just be

{"quality": 24.5, "regional": -23.0, ...}

As for what information it needs, I'm writing this quickly so don't hold me to this, but:

• Quality requires just the rankings of the adjudicators on the panel. It's assumed that the chair is the highest-ranking (or highest-equal) judge.
• Representation scores require (just) regions, genders and languages of teams and judges.

Did you want history and conflict scores or were you doing this by color-coding from the conflict/history JSON files?

Ideally we would provide a way for you to pass the Debate and AdjudicatorPanel objects, but I don't think this is a shorter route. More realistically I'd parse a simplified JSON, I guess. Or I'd finally implement an "import JSON API" library that you export from Ember, and use it to create the objects. I'll try and do that on the plane.

Enable swappable panels

IE dragging entire panel blocks to swap two sets of chairs/panellists/trainees

Front End Critical Path

Julia Dependent:

• 1 Need a current and maximum round value in order to calculate severity of history conflicts. Not sure how you want to loads these in — maybe a separate roundinfo.json? I could hardcode the maximum rounds and infer the current round from the histories if need be
• 2 Need team points and venues for each debate
• 3 Need each teams' deficit in teams.json if that is going to be useful to display on the front end
• 4 Need a julia function to call into to recalculate panel's representation scores on the fly as adjs move around. Also need guidance on what parameters to provide to the function
• 5 If highlighting teams close to breaking on the front end is important I need either a toggle/value for each team that represents this, or a simple algorithm I can put into JS
• 6 Stress test the UI at WUDC scale levels of panels and allocation iterations. Requires a 100 room data set with allocations
• 7 For adjs that have multiple institutional conflicts I need a data structure that indicates this. I have a slight preference for an adjinstitution.json that just lists all of these conflicts in a similar manner to the other conflict types (even if most of them can be inferred)

Frontend Dependent

• Swappable panels
• Disallow dragging between different allocations
• Fix the top bar design
• Indicate severity of history conflicts
• Fix in-panel institutional conflicts

Front > Backend > Julia (and back again!) interface

Ok, so what I think will work is this. Anyway data wants to go from the front end to Julia (IE the weightings for running an allocation, or a list of debates and their human-assigned importances):

1. The frontend triggers an action that wraps its model/data up into a dictionary that is POST'd to a backend route.
   • Example of an action/post = createAllocation in frontend/app/routes/index.js
2. The backend receives the post at a specified router.
   • Example of receive= post('/debate-importances/' in backend/routes/index.js

Two things can happen then. The data can be passed to a julia function as parameters, or written to a JSON file, which Julia can then be trigger to read. Or some combination for the two.
- In the same place as (2) there are examples of the file-writing and arg-passing processes

What this means for the critical path (end goal of testing/refining the algorithm)

• From what I understand, we're all good for getting data into the front end, tabbie2 or others
• After data is loaded, importances are set and exported to the backend
• After data is loaded, weightings are set and exported to the backend
• Julia needs to either read from the backend/data/debate-importancesor the backend route needs to pass it an array of these parameters into whatever function creates an allocation (alongside the weighting values).
• The backend needs to listen for when Julia finishes and load the allocation data back in to the frontend (this is trivial, just waiting on the above item to be finalised).

What this means for the critical path (end goal doing real allocations):

• Locks and bans need to be exported alongside the debate importances
• Panels need to dynamically communicate the parameters that determine their representational strengths to julia and julia needs to return a value. Setting up this post/route should be easy on my end.

I suspect in most cases it will be easiest just to pass the data to julia as parameters, as the julia functions must already take said parameters, or could easily be made to do so. Perhaps you could create an interfaces.jl that contains the backend-accessble functions?

Alert users when tasks such as loadinge/exporting data start and finish