Tinkering #2: The Play's The Thing

[lederhosen]

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:

# Problem: we're trying to cast a play, with more parts than actors.
# Some actors will have multiple parts, but we can't have one actor
# playing two parts in the same scene.
# Subject to that restriction, we want to give out a good balance of
# part so that players have approximately the same number of lines.
# We also want to avoid quick changes, where an actor plays two
# different parts in consecutive scenes, but we'll tolerate them if
# unavoidable.

# Here we declare what our inputs will be. We'll have a list of
# actors, parts, and scenes:
set Actors;
set Parts;
set Scenes ordered;
# The "ordered" property lets us work with the concept of "next
# scene" to check for things like quick changes - though I haven't
# yet implemented these.

set FightTrainedActors;
set PartsReqFightTraining;

# We will indicate how many lines each character has.
# To save counting up lines for every minor role, we'll declare
# that lines by part will be treated as ~ 5 lines except where
# otherwise specified:
param LinesByPart{Parts} default 5;

# And we'll note each part that appears within each scene.
# These are entered as pairs of scenes and parts.
set AppearingInScene within {Scenes, Parts};

# Decisions will be represented by a binary array "Casting":
# Casting[a,p] is 1 if actor a plays part p, 0 otherwise.
var Casting {a in Actors, p in Parts} binary;

# Each part should be allocated to exactly one actor;
subject to AllocateAllPartsOnce {p in Parts}: sum{a in Actors}(Casting[a,p]) = 1;
# If it turns out to be impossible to solve under this constraint,
# we might consider changing this to allow the same part to be played
# by two different actors, with a penalty for switching.

# No actor should play two parts in a single scene
subject to OnePartPerScene {a in Actors, s in Scenes}:
sum{(s,p) in AppearingInScene} (Casting[a,p]) <=1;
# similarly, if we have too few actors to satisfy this, we might
# consider replacing the hard constraint with a hefty penalty.

# Constraints specific to the play can be included in the .dat file:

# We want to balance out the roles so that each actor gets a
# reasonable share of the spotlight. A good way to do this is
# by tallying up total lines by actor, and minimising the sum
# of squares of those counts:

minimize ObjectiveFunction: sum{a in Actors}
((sum{p in Parts} Casting[a,p]*LinesByPart[p])^2) ;

hamlet.dat:

# Let's cast Hamlet!
# Scene info from https://www.playshakespeare.com/hamlet/scenes

set Actors := Art Bea Chris Derek Eve
Frank Greg Hugh Irene Jo
Kate Luke Meg Ned Oli
;
# Act 3 scene 2 has 15 characters on stage, so we
# know we'll need at least 15 actors.
set Parts :=
Attendant1
Attendant2
Barnardo
Captain
Claudius
Clown1
Clown2
Cornelius
DoctorDivinity
EnglishAmbassador
Fortinbras
Francisco
Gentleman
Gertrude
Ghost
Guard
Guildenstern
Hamlet
Horatio
Laertes
LaertesFollower1
LaertesFollower2
Lord1
Lord2
Lucianus
Marcellus
Messenger
Ophelia
Osric
PlayerKing
PlayerLucianus
PlayerPrologue
PlayerQueen
Polonius
Reynaldo
Rosencrantz
Sailor1
Sailor2
Voltemand ;


# Lines by part. These are just estimates I made up, I didn't count them -
# as long as they give a good comparison of the different characters'
# importance this should be good enough.
# Remember, if not otherwise stated, characters will default to 5 lines.
param LinesByPart:=
Claudius 200
Gertrude 200
Ghost 50
Guildenstern 100
Rosencrantz 100
Hamlet 500
Laertes 100
Ophelia 150
Polonius 100
Horatio 50
PlayerKing 10
PlayerQueen 10
;

set Scenes =
1_1 1_2 1_3 1_4 1_5
2_1 2_2
3_1 3_2 3_3 3_4
4_1 4_2 4_3 4_4 4_5 4_6 4_7
5_1 5_2;


# identify each part in each scene where they appear
set AppearingInScene :=
1_1 Barnardo
1_1 Francisco
1_1 Horatio
1_1 Marcellus
1_1 Ghost
1_2 Claudius
1_2 Gertrude
1_2 Polonius
1_2 Laertes
1_2 Hamlet
1_2 Voltemand
1_2 Cornelius
1_2 Horatio
1_2 Marcellus
1_2 Barnardo
1_3 Laertes
1_3 Ophelia
1_3 Polonius
1_4 Hamlet
1_4 Horatio
1_4 Marcellus
1_4 Ghost
1_5 Hamlet
1_5 Horatio
1_5 Marcellus
1_5 Ghost
2_1 Polonius
2_1 Reynaldo
2_1 Ophelia
2_2 Claudius
2_2 Gertrude
2_2 Hamlet
2_2 Rosencrantz
2_2 Guildenstern
2_2 Polonius
2_2 Voltemand
2_2 Cornelius
2_2 Attendant1
2_2 Attendant2
2_2 PlayerKing
2_2 PlayerQueen
2_2 PlayerPrologue
2_2 PlayerLucianus
3_1 Claudius
3_1 Gertrude
3_1 Polonius
3_1 Ophelia
3_1 Rosencrantz
3_1 Guildenstern
3_1 Lord1
3_1 Lord2
3_1 Hamlet
3_2 Hamlet
3_2 Polonius
3_2 Guildenstern
3_2 Rosencrantz
3_2 Horatio
3_2 Claudius
3_2 Gertrude
3_2 Ophelia
3_2 Lord1
3_2 Lord2
3_2 Guard
3_2 PlayerKing
3_2 PlayerQueen
3_2 PlayerPrologue
3_2 Lucianus
3_3 Claudius
3_3 Rosencrantz
3_3 Guildenstern
3_3 Polonius
3_3 Hamlet
3_4 Gertrude
3_4 Polonius
3_4 Hamlet
3_4 Ghost
4_1 Claudius
4_1 Gertrude
4_1 Rosencrantz
4_1 Guildenstern
4_2 Hamlet
4_2 Rosencrantz
4_2 Guildenstern
4_3 Claudius
4_3 Attendant1
4_3 Attendant2
4_3 Rosencrantz
4_3 Guildenstern
4_3 Hamlet
4_4 Fortinbras
4_4 Captain
4_4 Hamlet
4_4 Rosencrantz
4_4 Guildenstern
4_5 Horatio
4_5 Gertrude
4_5 Gentleman
4_5 Ophelia
4_5 Claudius
4_5 Messenger
4_5 Laertes
4_5 LaertesFollower1
4_5 LaertesFollower2
4_6 Horatio
4_6 Gentleman
4_6 Sailor1
4_6 Sailor2
4_7 Claudius
4_7 Laertes
4_7 Gertrude
4_7 Messenger
5_1 Clown1
5_1 Clown2
5_1 Hamlet
5_1 Horatio
5_1 Claudius
5_1 Gertrude
5_1 Laertes
5_1 DoctorDivinity
5_1 Lord1
5_1 Lord2
5_1 Attendant1
5_1 Attendant2
5_2 Hamlet
5_2 Horatio
5_2 Osric
5_2 Lord1
5_2 Claudius
5_2 Gertrude
5_2 Laertes
5_2 Fortinbras
5_2 EnglishAmbassador
5_2 Attendant1
5_2 Attendant2
;


# We can include play-specific constraints here. For example, Hamlet
# requires stage fencing between Hamlet and Laertes, so we want to restrict
# those roles to actors with appropriate training.

set FightTrainedActors := Chris Eve Hugh Luke;
set PartsReqFightTraining := Hamlet Laertes;

subject to EnforceFightTraining {a in Actors diff FightTrainedActors, p in PartsReqFightTraining}:
Casting[a,p] = 0;
# that is: for any actor *not* in the list of fight-trained actors, they cannot
# be assigned to a role requiring that training.
# The same sort of format can be used to enter other role/actor
# compatibility requirements.

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.