In the UK we have a form of social dance called ceilidh dancing, which is super fun. A bit like contra dancing in the USA if you’re familiar with that.
Ceilidhs are “called” by a “caller” whose job is to decide which dances to do and then instruct how to do them.
I want to make it easier to create fun set-lists of dances for ceilidhs.
The set-up is that I’ll have a list of dances (hundreds) to choose from. Each dance has a bunch of attributes, mostly binary (such as whether or not a certain move appears) but also categorical (such as the broad type of dance) and continuous (such as how long it is).
The challenge is to make a list of dances, with restrictions such as:
The dances must all be different
There should be a wide variety of moves
There should be a wide variety of types
Adjacent dances shouldn’t be too similar
The total number or length of the dances should be some target
Sometimes I’ll want all the dances to be fairly easy, sometimes I’ll want a more difficult set-list, depending on the audience
I might need to include some certain dances
I described this as optimisation-ish because I don’t necessarily want the absolute optimal set-list, I want a variety of pretty-good set-lists.
I know very little about this sort of optimisation or where in the Julia ecosystem to begin. Any pointers?
Seems more like random sampling than optimization? That is, if you have a way to randomly generate dances, then you can just generate a large number. Then have some similarity measure so that you can discard dances that are sufficiently similar to other ones. And devise a difficulty measure so that you can sort them by approximate difficulty.
(It seems like people have already written code to randomly generate contra dances, e.g. this page.)
Yes I suppose it is a sampling question as well as an optimisation one - they are strongly related topics I think.
In that case - how do I sample among all lists of dances, where I have an objective function for what is a good set-list and I only want to sample sufficiently good ones (which might be a vanishingly small proportion of all possible set-lists)? Simple rejection sampling won’t cut it I think. Is MCMC appropriate? I’m also not an expert on sampling.
(Also note the dances themselves are not random - there will be a finite set of possibilities.)
My 2 cents from working on “practical” optimization problems like this is that you might find it easier to start by formulating the constraints, and using a constraint solver or some other method to sample feasible solutions without worrying about an objective function. Then after you are sure the constraints are producing set lists that are feasible, go ahead and start tackling the objective.
Also, don’t be afraid to think outside the box. Maybe your problem is a graph coloring problem in disguise? Maybe it would be best expressed in something like Prolog? Who knows.