私は現在、スポーツ チームのスケジューリングの問題を解決しようとしています。私の決定変数は次のように宣言されています。
dvar int plays[Games][0..1] in Teams;
この特定のケースでは、どこGamesからの範囲で0..19あり、からTeamsの範囲です。0..9これは、どのチームが各ゲームをプレイしているかを表す 20 行 2 列の行列を形成します。
[
[3, 7],
[2, 4],
[9, 1]
]
これは、チーム 3 が最初のゲームでチーム 7 と対戦し、次にチーム 2 対チーム 4 と対戦し、チーム 9 対チーム 1 で終了することを示す 3 ゲーム マトリックスの例です。
私の制約では、各チームがほぼ同じ数のゲームをプレイする必要があることを表現しようとしています。この制約を表現する私の試みは次のとおりです。
subject to {
gameBalance:
standardDeviation(all(t in Teams) count(all(g in Games, s in 0..1) plays[g][s], t)) < 1;
}
[18, 18, 0, 0, 0, 0, 0, 0, 0]この定式化は健全であると信じていますが、CPLEXが 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, ...]上記と同じ簡単な解決策で合格しました。3に変更2.999...することで、モデルは実行不可能になりました。したがって、私が計算した標準偏差は、制約で 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.
最終的に、私の質問は次のとおりです。
- 私は OPL の規則に違反していて、ステートメントを使用してはいけませんか?
- 上記に「はい」の場合、私が探している制約を表現する合法的で有効な方法はありますか?
- 上記に当てはまらない場合、OPL が制約の標準偏差を計算できないのはなぜですか?