创建最大数量的括号

问题描述 投票：0回答：1

我已经参加了我的保龄球联赛。这是一个小联盟，只有 60 人（12 支球队）。每周我们打三场比赛。每个人都可以分在多个括号中，因为他们的分数在某种程度上并不取决于他们与谁一起在泳道上。

我每周都会询问谁想要在括号中以及他们想要在括号中。所以典型的输入看起来像

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

也就是说，有二十个人想要进入括号。大多数人希望只进入一个括号，少数人希望最多进入 2 个括号，一个人希望最多进入 3 个括号，还有 6 个人希望进入尽可能多的括号。

还有一些额外的限制使这变得更有趣：

  1. 任何人都不应该在同一个括号中两次 - 某人在任何时候都必须与自己匹配是没有意义的。
  2. 在最初的播种中，任何人都不应在多个分组中与同一个人配对 - 例如如果 Bob 和 Joe 在括号 A 中匹配，那么他们不应该在任何其他括号中匹配。
  3. 我们应该“公平”地将人们放在括号中 3a.在将任何人放入第二个括号之前，我们应该将每个人至少放入一个括号中 - 例如如果我们有 16 个人，其中 15 人想要在一个括号中，而 1 个人想要在 2 个括号中，那么我们应该使用所有 16 个人，而不是在两个括号中都使用该人，而将某人排除在外。 3b. （可选，很高兴拥有）我们应该尝试尽可能公平地将人们放在尽可能多的括号中 - 例如如果 3 个人要求分在 5 个括号中，我们可以选择将其中 2 个放入 5 个括号中，将第三个放入 3 个括号中，或者将他们全部放入 4 个括号中，那么我们应该将他们全部放入 4 个括号中。

起初我只是随机将人播种在括号中。但在上面的示例中，大多数情况下最多会生成 5 个括号。尝试生成所有可能的解决方案来找到可能的最大括号数是不可行的，因为解决方案空间太大。我问了一些同事，他们建议尝试一下 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 来查看可以创建多少个括号。我不太介意，但是当尝试使用 
maxBrackets = 9
时，它并没有告诉我它不能令人满意，而是运行了很长一段时间，所以我最终停止了它。显然，它试图在一个巨大的潜在空间中找到一个解决方案，但无法找到一个解决方案，但在没有完成搜索的情况下，不能证明不存在解决方案。我想知道是否有人找到了改进模型的方法，或者有一个完全不同的模型的想法，可以使这项工作更好。否则我只需要对运行 MiniZinc 设置一个时间限制（大约 20 秒）。

solver minizinc
1个回答
0
投票

我能够找到一个满足这两个缺失要求的解决方案。

我做了两个关键的改变：

  1. 我们现在有 
    array[Bracket,Slot] of var Bowler: brackets
    ，而不是 
    array[1..maxBrackets,Bowler] of var 0..numEntrants: brackets
    。这种使任何非零值成为逆的穿梭变换简化了约束，我相信它缩小了解决方案空间，允许更快地找到解决方案，甚至可以确定它是否在短时间内无法满足。
  2. 为了找到最大化括号数量的解决方案，我将 
    brackets
    数组保持在最大括号数量的固定大小，但引入了一个变量 
    numBrackets
    ，它用于绑定我们实际尝试的括号数量在
    brackets
    内创建。这意味着我们以前使用 
    brkt in 1..maxBrackets
    查看括号的地方，现在都使用 
    brkt in 1..numBrackets
    。这确实需要我们小心地将我们不使用的 
    brackets
    中的值限制为零，但这非常简单。

使用 OR-Tools 作为求解器，我们可以使用原始输入在短短几秒钟内找到解决方案 

numBrackets = 8
。

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;
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.