使用 Choco (CSP) 建模网球比赛

Question

我正在尝试用 Choco 建模问题以获得网球赛事（或任何运动）中可能的对决组合。

我尝试这样做的方式如下：

// Set of timeslots when the event is held (i.e. 10am-10pm)
int nTimeslots = 12;

// Courts available: court #1, #2 and #3
int nCourts = 3;

String[] players = { "Novak", "Andy", "Roger", "Stan", "Rafel", "Kei", "Tomas", "David" };
int nPlayers = players.length;

// Timeslots when each player cannot play for whatever reason
int[][] unavailability = {
    { 0, 1, 5 },
    { 8, 10, 11 },
    { 1, 2, 11 },
    { 0, 1 },
    { 2, 3, 4, 5, 6 },
    { 3, 4, 9, 10, 11 },
    { 4, 5 },
    { 2, 3 }
};

// Number of timeslots each match will occupy
int matchDuration = 2;

// This will hold the final combinations
// rows -> players, columns -> timeslots, matches[i][j] -> court where the player plays at that timeslot (0 means the player does not play at that time)
IntVar[][] matches;

我的主要问题是，对于此设置，我想不出一种方法来定义我的问题。我一直在这上面花了几天时间，但没有成功。我似乎遇到了一些类似的问题，但应该组合的不同元素的数量较少，通常是 1 或 2，但在我的问题中有 3 个：球员、时间段和球场。

在这上面花了很多时间之后，我不能比这更进一步了：

for (int player = 0; player < nPlayers; player++) {
    for (int timeslot = 0; timeslot < nTimeslots; timeslot++) {
        for (int playerUnavailbleTimeslot : unavailability[player]) {
            if (playerUnavailbleTimeslot != timeslot) {
                solver.post(IntConstraintFactory.arithm(matches[player][playerUnavailbleTimeslot], ">=", 0));
            } else {
                for (int i = 0; i < matchDuration; i++)
                    if (playerUnavailbleTimeslot - i >= 0)
                        solver.post(IntConstraintFactory.arithm(matches[player][playerUnavailbleTimeslot - i], "=", 0));
            }
        }
    }
}

IntVar matchesSum = VariableFactory.enumerated("Matches sum", 1 * matchDuration, nCourts * matchDuration, solver);
for (int player = 0; player < nPlayers; player++) {
    solver.post(IntConstraintFactory.sum(matches[player], matchesSum));
    //solver.post(IntConstraintFactory.nvalues(matches[player], VariableFactory.fixed(2, solver)));
}

第一个双循环只是将玩家不可用的那些时间段强制为 0（加上基于比赛持续时间值的范围），如果他可用则大于或等于。这样最终的矩阵开始看起来像这样：

0 0 ? ? ? 0 ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? 0 0 0 0 ?
.........................

然后我只确保每个球员的时间段中的值之和介于数字最小的球场乘以比赛持续时间和数字最大的球场乘以比赛持续时间之间。这是我想到的限制条件之一，所以每一行看起来像这样，例如，玩家 0 在时间段 3 和 4 上场 2：

0 0 0 2 2 0 0 0 0 0 0 0

我尝试定义约束 nvalues 应该强制执行不超过 n 不同的值符合数组，但是如果我像上面看到的那样使用它，问题只会呈现一个解决方案（什么？！）。

但是我需要定义更多的约束我什至不知道如何开始:

对于每一行，球员所在的场地必须有连续的编号，如果确实分配了该场地的话
对于每一行，我只能有 0 和法院编号 [1 - nCourts]
列应该配对以创建一对玩家之间的比赛。
同一个场地不能在同一时间段范围内配对超过一次（意味着同一时间场地内最多只能进行一场比赛）

这是我能想到的所有限制，但我相信还有更多。

我希望有任何建议可以帮助我继续这样做，因为现在我感到完全无能为力，而且关于 Choco 的在线信息几乎为零，可以帮助我解决这个问题。

Answer 1

我会先用数学写下你想要的东西。

不确定这是否有帮助，但这是我的实现，将其作为一个数学规划问题来解决。它没有使用约束编程，但看起来与您在 Choco 中所做的类似：

我尝试最大化玩家的最小游戏数，所以我们不会有人玩零游戏。可以想出很多变化，比如不是一直和同一个人对战等等

结果如下：

table中的数字为球场号码（-1表示不允许）。在这个时间表中每个人玩三遍。

使用 Choco (CSP) 建模网球比赛

Modeling tennis matchups with Choco (CSP)

java

constraints

constraint-programming

choco