Search code examples
minizinccp-sat

Creating the maximum number of brackets

I've taken on running brackets on my bowling league. It's small league, just 60 people (12 teams). Every week we bowl three games. Each person can be in multiple brackets as their scores are not, to a certain extent, determined by who they are on the lanes with.

I go around each week and ask who wants to be in brackets and how many they want to be in. So a typical input would look like

array[_] of 1..maxEntries: reqEntries = 
  [ 1, maxEntries, 2, maxEntries, 1, 1, maxEntries, 1, 2, maxEntries, 1, 1, 3, maxEntries, 2, 1, 1, maxEntries, 1, 2 
  ];

That is, twenty people want to get into brackets. Most want to get into just one bracket, a few want to be in at most 2 brackets, one wants to get into at most 3 brackets, and six people want to be in as many brackets as we can place them in.

There are a few additional constraints that make this a bit more interesting:

  1. No one should be in the same bracket twice - it wouldn't make sense for someone to have to matchup with themselves at any point.
  2. In the initial seeding, no one should be matched up with the same person in more than one bracket - e.g. if Bob and Joe are matched up in bracket A they should not be matched up in any others.
  3. We should place people in brackets "fairly" 3a. We should place everyone in at least one bracket before placing anyone in a second bracket - e.g. if we have 16 people and 15 of them want to be in a single bracket and 1 wants to be in 2 brackets, we should use all 16 people instead of using that person in both brackets and leaving someone out. 3b. (optional, nice to have) We should try and be as fair as possible about placing people in as many brackets as possible - e.g. if 3 people request to be in 5 brackets and we have a choice of placing 2 of them in 5 and the third in 3 or placing them all in 4, we should place them all in 4.

At first I was just randomly seeding people in brackets. But in the above example, that results in at most 5 brackets being generated most of the time. Trying to generate all possible solutions to find the maximum number of brackets possible is not viable because the solution space is so large. I asked some colleagues and they suggested giving MiniZinc a try.

After trying a couple of different approaches, I've come up with the following

include "alldifferent.mzn";
include "member.mzn";

int: maxBrackets = 8;
int: maxEntries = maxBrackets;

array[_] of 1..maxEntries: reqEntries = 
  [ 1, maxEntries, 2, maxEntries, 1, 1, maxEntries, 1, 2, maxEntries, 1, 1, 3, maxEntries, 2, 1, 1, maxEntries, 1, 2 ];

set of int: Bowler = index_set(reqEntries);
set of int: Bracket = 1 .. maxBrackets;
set of int: Slot = 1..8;

array[Bracket,Slot] of var Bowler: brackets;

array[Bowler] of var 1..maxEntries: entries;

% everyone should go in a bracket 
% and actual entries should not exceed the requested entries
% and "store" the count for output
constraint forall (bwl in Bowler)(
  let { var int: c = count(b in Bracket, s in Slot)(brackets[b, s] = bwl); }
  in 
    1 <= c
      /\ c <= reqEntries[bwl]
      /\ entries[bwl] = c
);

% each slot in each bracket is a different person
constraint forall (bkt in Bracket)(
  all_different(row(brackets, bkt))
);

% each matchup is unique
array[1..(maxBrackets*4)] of var set of Bowler: matchups;

constraint forall (bkt in Bracket, s in Slot)(
  let { var int: i = 4*(bkt - 1) + ceil(s / 2); }
  in card(matchups[i]) = 2 /\ member(matchups[i], brackets[bkt,s])
);

constraint all_different(matchups);

solve satisfy;

output 
  [ "reqEntries = "
  , show(reqEntries) 
  , "\nentries    = "
  , show(entries)
  , "\nbrackets = \n"
  , show2d(brackets)
  , "\nmatchups = \n"
  , show(matchups)
  ]

In the MiniZinc IDE on my MacOS laptop, OR Tools CP-SAT 9.11.4210 is able to find a solution in ~1.7s. HiGHS 1.7.2 is able to find a solution in ~13.5s.

Overall, I'm pretty happy with that result but I'd like to see if it can be improved. Mainly, what I'd like to be able to do is have it automatically find a solution which maximizes the number of brackets. With this solution, I'd have to try with maxBrackets equal to 6, 7, 8, or 9 to see how many brackets might be created. I wouldn't mind that so much, but when trying with maxBrackets = 9, instead of telling me it's not satisfiable, it just runs for a very long time so I end up stopping it. Obviously it is trying to find a solution in a large potential space and isn't able to find one, but can't provable say there isn't one without finishing the search. I'd like to know if anyone sees a way to improve the model or has an idea for a completely different model that might make this work better. Otherwise I'll just have to put a time limit on running MiniZinc (something like 20s).

Solution

  • I was able to find a solution which satisfied both the missing requirements.

    There are two key changes that I made:

    1. Instead of array[Bracket,Slot] of var Bowler: brackets, we now have array[1..maxBrackets,Bowler] of var 0..numEntrants: brackets. This shuttle shift of making any non-zero value an inverse simplifies the constraints and I believe it narrows the solution space, allowing solutions to be found much faster and even determine if it's unsatisfiable in a a short amount of time.
    2. To find a solution that maximizes the number of brackets, I kept the brackets array at the fixed size of the maximum number of brackets, but introduced a variable numBrackets, which is used to bound how many brackets we actually try to create within brackets. This means that everywhere we were looking at brackets using brkt in 1..maxBrackets, we now use brkt in 1..numBrackets. This does require that we're careful to constrain the values in brackets we aren't using to zero, but that's pretty simple.

    Using OR-Tools as the solver we are able to find a solution, with the original input, with numBrackets = 8 in just a few seconds.

    include "alldifferent.mzn";
include "nvalue_fn.mzn";

int: maxEntries = 10;

array[_] of 1..maxEntries: reqEntries;

int: totalEntries = sum(reqEntries);
int: numEntrants = length(reqEntries);

int: maxBrackets = totalEntries div 8;
int: minBrackets = numEntrants div 8;

set of int: Bowler = 1..numEntrants;

var int: numBrackets;

constraint (minBrackets <= numBrackets /\ numBrackets <= maxBrackets);

array[1..maxBrackets,Bowler] of var 0..numEntrants: brackets;

% brackets not in the solution should all be zero'd out
constraint forall(nonBkt in numBrackets+1..maxBrackets, bwl in Bowler)(
  brackets[nonBkt,bwl] = 0
);

% brackets can only have 8 people in them
constraint forall(bkt in 1 .. numBrackets)(
  count(bwl in Bowler)(brackets[bkt,bwl] != 0) = 8
);

% when a person is in a bracket, they are matched up with someone who is not themself
constraint forall(bkt in 1 .. numBrackets, bwl in Bowler)(
  brackets[bkt,bwl] != 0 -> 
    brackets[bkt, brackets[bkt, bwl]] = bwl /\ brackets[bkt, bwl] != bwl
);

array[Bowler] of var 0..maxEntries: entries;

% everyone is in a bracket if there enough brackets
% and they are not in any more than they requested
constraint forall(bwl in Bowler)(
  let { var int: c = count(bkt in 1..numBrackets)(brackets[bkt, bwl] != 0); }
  in 
    (numBrackets * 8 > numEntrants -> 0 < c)
      /\ c <= reqEntries[bwl]
      /\ entries[bwl] = c
);

constraint forall (bwl in Bowler)(
  all_different_except_0(col(brackets, bwl))
);

array[Bowler] of var int: leftovers;

constraint forall(bwl in Bowler)(
  leftovers[bwl] = reqEntries[bwl] - entries[bwl]
);

constraint forall(x in Bowler, y in Bowler)(
  (reqEntries[x] = reqEntries[y]) -> 
    leftovers[y] - 1 <= leftovers[x] /\ leftovers[x] <= leftovers[y] + 1
);

solve maximize numBrackets;