1
$\begingroup$

Hello,

I am in the process of building some software to generate fixtures for a chess league. Which has a little twist which complicates matters. I would like to introduce a constraint. Where by a team and the below team from a club are not allowed to play on the same night. e.g. Loughborough 1 is not allowed to play on the same night as Loughborough 2. This help teams share players, therefore play more games.

The league has five divisions, with 8, 7, 8, 7, 7 teams in respectively. The first half of the league is played over 10 weeks. This means that teams do not have to play each week.

A solution would be to brute force all the fixture combinations, for all the divisions. The problem with this approach is that there are way too many combinations!

I am wondering if there are any mathematical techniques that I could use to help me with this problem. I am not wanting to find a unique solution (a combination of fixtures, without violating the constraints). I would be happy with an algorithm which produced 10 violation of constraints in the season.

Any help or pointers would be greatly appreciated.

Can you suggest any areas for me to research.

Thanks in advance.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Crossposted to SE: math.stackexchange.com/questions/31996 Michael, you should know that it's considered impolite to post the same question in multiple forums without waiting for an answer in the first one; you don't want to make lots of people work hard to giving you a great answer just to hear you say "thanks, but I've already got it from another forum". $\endgroup$
    – Zev Chonoles
    Commented Apr 10, 2011 at 1:26
  • $\begingroup$ I am not a regular user of forums. Forgive me for not understanding the protocol. In hindsight, I do consider it impolite to post in two forums. I will certainly not make this mistake in the future. There doesn't seem an obvious way for me to close the question in the second site that I asked in. $\endgroup$
    – froogz3301
    Commented Apr 10, 2011 at 9:49
  • $\begingroup$ I have undertaken this challenge as I see it as interesting cross between computer science and mathematics. I haven't done any mathematical programming since the days of my degree. At this stage in my question. I would be really happy if someone would say, go and take a look at x, y, z branch of mathematics. $\endgroup$
    – froogz3301
    Commented Apr 10, 2011 at 9:52

1 Answer 1

Reset to default
1
$\begingroup$

This is an answer to the general advice part of the question rather than the specifics of the chess league problem.

I think the field of math to look at is that of Combinatorial Designs. Roughly speaking, this deals with arranging objects according to constraints and it has subfields that look particularly at various types of tournament/league design (I haven't come across anything that reminds me closely of your particular problem, but that's not good evidence that there isn't something out there already). If you can get access to The Handbook of Combinatorial Designs somehow, that will probably give you some good pointers. (I don't have a copy nearby at the moment to be more specific, sorry.)

The second area you could look at is from the computational side: hill-climbing algorithms. Implementing such an algorithm would mean that you did not have to search through all of the possible combinations, with the trade-off that you are not guaranteed the optimal result. The idea is that you ignore the extra constraint initially and generate a valid schedule. Then you successively tweak the schedule to reduce the number of times teams from the same club play on the same evening. If it doesn't get close enough, start over and try again. You'll need a method of generating initial schedules (which I guess you already have) and a method for tweaking that works nicely with the constraint (usually the difficult step).

Hope this helps.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the interesting ideas. This approach would be similar to how the person manually does it. I have hunted around for some material on these ideas. I will report back once I have a grasp of it. $\endgroup$
    – froogz3301
    Commented Apr 13, 2011 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .