5
$\begingroup$

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 whereby two consecutive teams from the same 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, and therefore play more games.

The league has five divisions, with 8, 7, 8, 7, 7 teams 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 violations of constraints in the season.

Any help or pointers would be greatly appreciated. Can anyone suggest any areas for me to research?

Improve this question
$\endgroup$
  • $\begingroup$ Does a team in a league of 8 have to play 7 times or 14 a season? Are matches the same night each week in every division, or can some or all of the seven nights be used? Can two teams from the same club be in the same division? Looking at your website, I would guess the answers might be 14, 3 nights a week, and yes. $\endgroup$ – Henry Apr 9 '11 at 23:52
  • $\begingroup$ Have you tried using swiss and then manually preventing groups from pairing against each other? The norm in chess is to prevent pairing until the very last round. $\endgroup$ – picakhu Apr 9 '11 at 23:54
  • $\begingroup$ @Henry A league of 8 has to play 14 times in a season. The matches are played on the club night of a team. Which are played Monday through to Thursday. $\endgroup$ – froogz3301 Apr 10 '11 at 9:31
  • $\begingroup$ @picakhu The problem with manually preventing groups is that there are too many combinations. Hence I am looking for an algoirithmic approach which I can implement in a computer program. $\endgroup$ – froogz3301 Apr 10 '11 at 9:34
  • $\begingroup$ How often does such a combination happen randomly? If you're lucky, you might get by with simply trying a few combinations until it works. $\endgroup$ – Yuval Filmus Apr 14 '11 at 4:26
1
$\begingroup$

Timetabling is something evolutionary strategy's can get solutions for pretty quickly with all kinds of limitations. Edinburgh university schedules all its courses/classes using an some ES software.

could probably use a basic genetic algorithm to get a good solution. Even better is with a GA you dont get A solution you get a population of solutions to pick the one you like best from!

Improve this answer
$\endgroup$
1
$\begingroup$

Why don't you constrain the generative process?

For each match-up: randomly select a valid pair of teams.

"Valid" pair meaning: teams which currently have less than 8 match-ups, and which are not adjacent in the same division. (Can also add, for instance, teams which have not played against each other yet.)

Cheers

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.