1

我目前正在尝试解决运动队的日程安排问题。我的决策变量声明为：

dvar int plays[Games][0..1] in Teams;

在这种特定情况下，范围从Games哪里开始，从哪里开始。这形成了一个 20 x 2 的矩阵，表示每场比赛的球队。0..19Teams0..9

[
  [3, 7],
  [2, 4],
  [9, 1]
]

是一个 3 场比赛矩阵的示例，它显示第 3 队在第一场比赛中对阵第 7 队，然后是第 2 队对第 4 队，最后以第 9 队对第 1 队结束。

在我的限制条件下，我试图表达每支球队应该打接近相同数量的比赛。我表达这个约束的尝试如下：

subject to {
    gameBalance:
    standardDeviation(all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t)) < 1;
}

我相信这个公式是合理的 - 但是，我觉得我遇到了某种未定义的行为，因为即使 CPLEX 说它返回[18, 18, 0, 0, 0, 0, 0, 0, 0]9 个团队案例的“最佳”解决方案，约束也没有得到满足。

手工计算，我得到一个标准差7.59，显然不小于 1。为了验证这一点，我将以下内容放在模型的结果数据部分：

int playcounts[Teams] = all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t);
float std = standardDeviation(all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t));

execute {
    writeln("counts: " + playcounts);
    writeln("std: " + std);
}

这给出了以下输出：

// solution with objective 0
counts:  [18 18 0 0 0 0 0 0 0]
std: 7.48331477

这进一步证实了我写的关于约束的一些事情是不正确的。为了进一步调试这种情况，我使用了以下约束：

standardDeviation(foo) < 1;

Wherefoo被声明为一个整数数组[1, 100, 10000, 1000000, 100000000]- 它的标准偏差绝对不小于 1。正如预期的那样，该模型被证明是不可行的，这表明标准偏差按预期工作，因此问题必须在我构建计数数组的方式。然后我尝试了以下约束：

standardDeviation(all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t)) + 2.999999999 < 3;

我的理论是，如果标准偏差被处理为非零，那么这应该会使模型不可行。令我惊讶的是，该模型以上述相同的简单[18, 18, 0, ...]解决方案通过。通过更改2.999...为 3，模型不可行。因此，我得出结论，我计算的标准偏差在约束中评估为 0，但在搜索结束后，它在结果数据部分中被正确计算。

在这一点上，我确信问题源于我计算计数数组all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t)（playcounts以上）。

此外，以下约束非常有效：

// The total number of games played must be exactly 36
sum(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t) == 36;

这使我相信问题在于all(t in Teams)...约束的一部分。为了检验这个理论，我使用了以下约束：

// The number of games the first team plays must be exactly 18
(all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t))[0] == 18;

理论上，这应该是一个多余的约束，因为返回的平凡解决方案以[18, 18, 0, ...]. 令我惊讶的是，这创造了一个不可行的模型。即使用== 0代替== 18，该模型仍然不可行。因此，我想弄清楚这个数字在评估什么。为此，我添加了以下决策变量：

dvar int a;

并将目标函数更改为：

maximize a;

具有以下约束：

(all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t))[0] == a;

这导致了一个具有最佳解决方案的模型。解决方案已a设置为-9007199254740991。如果我尝试使用minimize此模型，则会发生相同的结果。

如果我尝试约束a为非负数，那么 CPLEX 崩溃并带有### UNEXPECTED ERROR.

最后，我的问题是：

  1. 我是否违反了 OPL 的某些规则并以我不应该的方式使用语句？
  2. 如果以上是肯定的，是否有一种合法、有效的方式来表达我正在寻找的约束？
  3. 如果以上都不是，那么为什么 OPL 无法计算我的约束中的标准偏差？
4

0 回答 0