Tinkering: using AMPL/Gurobi to allocate parts in a play

Now and then Rey and I do play readings with friends. Usually there are rather more roles than there are readers, so "one man in his time plays many parts", which works fine until you end up playing two roles in the same scene and having to have an extended conversation with yourself.

So you want to cast roles in a way that avoids that kind of overlap, and you probably also want to make sure the different readers each get a decent share of the lines. You could do this by hand, but since I'm currently teaching myself AMPL, I thought it'd be a fun challenge to program a solution.

AMPL (A Mathematical Programming Language) is similar to MiniZinc, which I posted about a while back: it's designed for specifying optimisation/constraint problems and then passing them to a solver of one's choice.

It's very much a declarative language: instead of giving the computer a set of steps to follow, you give it a set of requirements and then let it figure out how to satisfy those requirements. (This still feels like magic to me.)

AMPL and other optimisation languages usually take input in two parts: a "model" which is a generic description of the problem and requirements, and "data" which defines a specific instance of the problem.

So, here's some AMPL code:

( The model )

( The data: )

In the unlikely event that anybody other than me actually wants to use this, you can download a free demo from AMPL (unlimited duration, restricts to about 300 variables i.e. number of actors x number of parts should be less than 300).

The demo comes bundled with a selection of top-notch and open-source commercial solvers, all free to use subject to that size restriction. By default it uses the MINOS solver, which is nice for generic nonlinear problems but doesn't handle integer constraints; since those are important here you'll want to use "options solver gurobi" (or cplex or xpress).

Tinkering #2: The Play's The Thing

So after yesterday's post I thought I'd extend it a little and test my code on a full-sized problem: casting Hamlet.

This helpful site lists the characters present in each scene, although you have to be a little careful - Claudius is also listed as "King", and Gertrude as "Queen". In some cases it just lists groups ("Assistants", "Clowns", etc.); for this work I've just assumed there are two of each, though you'd want to check that. This results in 39 parts.

I entered that data, along with some made-up numbers for how many lines each part has; the exact values don't matter too much, as long as there's enough info to distinguish between major and minor parts. I also tweaked it so that minor characters are assumed to have 5 lines each unless specified otherwise, which saves on data entry.

Unfortunately the demo license for AMPL doesn't allow me quite enough variables to solve this problem. (I could probably reformulate it to reduce it to one variable per part, plus a few extra, but that would be a bit messier.)

Not to fear, there's another option: NEOS. NEOS is a web service that allows anybody to submit optimisation jobs for free, without a size limitation... and it accepts AMPL format. Having tested and debugged my code on a smaller problem, I can then add the full Hamlet data and submit it to NEOS at this page.

I upload three files:

( castingmodel.mod )

( hamlet.dat )

Last, a commands file to tell NEOS what output I want:

casting_commands.txt:

solve;
display Casting;

I then enter my email address and click "submit". In a minute or two, NEOS shows me the results, which you can view for yourself, and also emails me a copy. (A result of "infeasible" would indicate that it's impossible to satisfy the problem as specified, either because of some inconsistency within the constraints or because there aren't enough actors.)

The output shows some information about the solution process, and at the bottom it gives the final casting:

Art: Guildenstern
Bea: Barnardo, Clown 2, English Ambassador, Player Queen, Reynaldo
Chris: Hamlet
Derek: Horatio, Player Lucianus
Eve: Doctor of Divinity, Fortinbras, Laertes Follower 2, Player King
Frank: Ophelia
Greg: Polonius
Hugh: Gertrude
Irene: Francisco, Gentleman, Lord2, Osric, Voltemand
Jo: Claudius
Kate: Clown 1, Rosencrantz
Luke: Laertes, Player Prologue
Meg: Captain, Cornelius, Laertes Follower 1, Lord 1, Sailor 2
Ned: Attendant 2, Ghost, Lucianus
Oli: Attendant 1, Guard, Marcellus, Messenger, Sailor 1

This looks pretty sensible overall: most actors either get one big part, or a bunch of small parts, and our choices for Hamlet and Laertes satisfy the fight training requirement.