lederhosen

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:

# 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.

# 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;
# not that we use the "ordered" property here, but it could
# be used if we wanted to extend the program e.g. to avoid
# having the same actor play two different characters in
# adjacent scenes
# We will indicate how many lines each character has
param LinesByPart{Parts};
# 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;

# We'll balance out the parts by looking at the minimum and
# maximum number of lines that the actors get.
var FewestLinesForActor;
var MostLinesForActor;

# define these two via constraints
subject to DefineFewest{a in Actors}: FewestLinesForActor <=
sum{p in Parts}(Casting[a,p]*LinesByPart[p]);
subject to DefineMost{a in Actors}: MostLinesForActor >=
sum{p in Parts}(Casting[a,p]*LinesByPart[p]);
# What we really want here is FewestLinesForActor = min{a in Actors}(sum{p in Parts}(...))
# but the min() operator would complicate matters because it's not a linear
# function, which makes it harder for the solver. Similarly we'd want MostLinesForActor
# = max(...).
# Because there are no other constraints on these variables, and the
# objective function is set up in such a way that increasing FewestLinesForActor
# or decreasing MostLinesForActor always improves it, we know that at the optimal
# solution these will in fact be exactly equal to respective min and max functions.

# 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.

# Our main objective is to maximize the lines for the actor with
# the fewest. However, there may be many different solutions which
# satisfy this: e.g. 100, 100, 1000 would be scored equally to 100,
# 500, 600 but the latter seems more balanced, so we might add a
# small penalty based on the largest part.
maximize ObjectiveFunction: FewestLinesForActor-0.01*MostLinesForActor;

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

# This will achieve similar results, and has the benefit of allowing us
# to get rid of FewestLines and MostLines variables, but it's a little
# less obvious to the reader and it requires a quadratic solver - which
# isn't a problem for Gurobi or CPLEX but might rule out some other options.

The data:

set Actors := Arthur Belle Chris;
set Parts := Vladimir Estragon Godot Rozencrantz Guildenstern;
param LinesByPart:=
Vladimir 150
Estragon 200
Godot 0
Rozencrantz 380
Guildenstern 275;

set Scenes = 1 2;

# identify each part in each scene where they appear
set AppearingInScene :=
1 Vladimir
1 Estragon
2 Rozencrantz
2 Guildenstern
;

# can add one-off constraints, e.g.:
subject to WePromisedChrisThisPart: Casting["Chris","Estragon"] = 1;

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).