如何优化MiniZinc模型以最大化保龄球联赛Bracket数量？

问题背景 #

负责运营一个60人（12支队伍）的小型保龄球联赛Bracket分组工作，每周进行3场比赛，选手可参与多个Bracket（得分不受同场选手影响）。每周收集选手参赛需求，示例输入如下：

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 
  ];

该示例对应20名选手参赛：多数仅需1个Bracket名额，部分最多2个，1名最多3个，6名希望尽可能多参与。

分组约束 #

• 选手不能在同一Bracket中重复出现；
• 任意两人不得在多个Bracket中配对；
• 公平分配：
  • 3a：先确保所有选手至少进入1个Bracket，再分配额外名额；
  • 3b：（可选）尽量公平分配参赛次数，如3人申请5个名额时，优先让每人都参与4次而非2人5次、1人3次。

现有MiniZinc模型 #

最初采用随机分组，最多生成5个Bracket，因解空间过大无法枚举全部解，遂采用MiniZinc构建模型，代码如下：

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

该模型在MacOS的MiniZinc IDE中，OR-Tools CP-SAT 9.11.4210求解耗时约1.7秒，HiGHS 1.7.2耗时约13.5秒。

当前问题与优化需求 #

• 需手动设置maxBrackets（如6、7、8、9）测试最大可生成的Bracket数量；
• 当maxBrackets设为9时，求解器长时间运行无法判定是否不可满足；
• 需要优化模型或重新建模，实现自动最大化Bracket数量，并提升求解效率。

内容的提问来源于stack exchange，提问作者purefn