スポーツスケジューリング — トーナメント表作成問題における組合せ論—

松井知己 (東京大学大学院情報理工学系研究科数理情報学専攻)

1 はじめに

「アメリカ大リーグの 2005 年スケジュールは, カーネギーメロン大学のトリック教授のグループが作成したものを採用することになった.」最近の読売新聞 [38] で, このニュースをご覧になった方も多いと思う. ここでトリック教授というのは, 2002 年に INFORMS の会長だった Michael Trick のことを指している. このように欧米では, 研究者がスポーツ競技のスケジュール作成を行うことが増えてきている. アメリカ大リーグ以外にも, ここ数年ではブラジルのプロサッカーリーグ (Ribeiro, Urrutia [25]), アメリカ西海岸大学対抗バスケットボール (Nemhauser, Trick [23]), ドイツのプロサッカーリーグ (Bartsch, Drexl, Kröger [3]) など, 大規模なスポーツ競技団体を含むさまざまな実例がある. 数理的な手法を用いたプロスポーツ競技のスケジュール作成の波は, やがて日本にも上陸することだろう.

スポーツ競技における対戦順序, 競技施設の割当などをうまく決定し, 質の良いスケジュールを作成する分野は, スポーツスケジューリングと呼ばれている. スポーツスケジューリングの研究は, 1970 年代ころから散発的に行われていたが, ここ数年で特に研究が活発化してきた. 本稿では, スポーツスケジューリングの最近の研究を中心に紹介する. スポーツスケジューリングに関しては, 文献 [12, 15, 16, 18] などを参照されたい. なお, 本稿で述べるスケジュールの形式は, 全てリーグ戦形式である. トーナメント形式の実用スケジューリング手法に関しては, Rokosz による文献 [26] を参照されたい.

2 基準スケジュール

本稿では, 次のような総当りリーグ戦のスケジューリングについて考える:

• チーム数は偶数 (以下 2n とする);

• 各チームは他の 2n − 1 チームと 1 回ずつ対戦を行う;

• 全てのチームが 1 日 (あるいは 1 週間など) に 1 回試合を行い, 2n − 1 日でリーグ戦が終了する.

本稿では, チームの集合を T = {1, 2, …, 2n} とする. また試合が行われる日 (時間帯) をスロットと呼び, スロットの集合を S = {1, 2, …, 2n − 1} で表す. プロスポーツ競技における総当りリーグ戦では, 各チームが本拠地を持っており, 各試合はどこかのチームの本拠地で開催されることが多い. 以下, 7–6 節では, 次の条件の下で総当りリーグ戦が行われるとする:

• 各チームはそれぞれ相異なる本拠地を持つ;

• 各試合は, 対戦する 2 チームのどちらかの本拠地で行われる.

図 1 は, 上記の条件を満たすスケジュールの一例である. スケジュールのそれぞれの行は各チームに対応し, 行内の数字は日ごとの対戦相手を表している. 図 1 のスケジュールでは, チーム 1 は 1 日目にチーム 3 と

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 1  3  @4  5  @6  2 2  @5  6  \underline{4}  \underline{3}  @1 3  @1  5  @6  @\underline{2}  4 4  @6  1  @2  5  @3 5  2  @3  @\underline{1}  @\underline{4}  6 6  4  @2  3  \underline{1}  @5 図 1: チーム数 6 のスケジュール

[figure: 6; 6; 6; 6; 6; 1; 2; 3; 4; 5; 1 日目; 2; 3; 4; 5; 1; 2 日目; 3; 4; 5; 1; 2; 3 日目; 4; 5; 1; 2; 3; 4 日目; 5; 1; 2; 3; 4; 5 日目]図 2: チーム数 6 の基準スケジュール.

対戦し, 以下チーム 4, 5, 6, 2 の順序で試合を行っていく. 各試合の前にある@の記号は, その試合が対戦相手の本拠地で行われることを示している. つまり, チーム 1 はチーム 4 と 2 日目に試合を行うが, この試合はチーム 4 の本拠地で行われる. 逆に@がついていない試合は, 自チームの本拠地で行われる. それぞれのチームにとっての本拠地をホーム, それに対して他チームの本拠地をアウェイと呼ぶ. また各チームにとって, ホームでの試合をホームゲーム, アウェイでの試合をアウェイゲームと呼ぶ.

実際の例では, 各チーム対が, 双方の本拠地で 1 回ずつ戦う, 2 重総当たり戦という方法をとることも多い (この場合, 試合数は全部で 2n(2n − 1) となる). 2 重総当たり戦に対しては, 以下のミラーリングという操作を用いることが多いようである [23,31]. これは, 総当たり戦のスケジュールをたてた後, 各試合を行う対戦会場のみを交換したスケジュールを, 後半に付けるという操作である. ミラーリングがしばしば用いられる理由は, 「同じチーム対の戦いはできるだけ離れた日程で行った方が, 観客にとって魅力的である」ことと, 「全試合日程の前半部で, すべてのチーム対が戦うことができる」ためのようである. 以下本稿では, 特に断らない限りは一重総当り戦について扱う.

チーム数が 2n の総当たり戦で, 毎日 n 試合を平行して行い, 2n − 1 日で全試合を行うスケジュールを, 実行可能スケジュールと呼ぶ. 任意の正の偶数 2n に対して, 実行可能スケジュールは存在する. これは, 例えば以下の手続きで作ることができる.

図 4 に示すように, チーム 1, 2, …, 2n − 1 を半径 1 の円周上に等間隔に並べ, チーム 2n を円の中心に配置する. 平行な矢印を n − 1 本, 向きを互い違いに並べ, それと垂直な半径に対応する線分を書いた円盤を用意する. 矢印の両端のチームが試合をするチーム対を表し, 矢印の根元のチームの本拠地で行うとする. この円盤を先ほどの円の上で 1/(2n − 1) 周ずつ回転させて, 各日の試合を決定する (図 2 では番号を回転させている). ただし後述する理由で, 半径に対応する線分の矢印は, 円盤の回転毎に反転させる正確には以下のように記述される; 第 t 日目に戦うチーム対は, {{2n, t}, {t + 1, t − 1}, {t + 2, t − 2}, …, {t + n − 1, t − n + 1}} であり (ただし t − k, t + k はモジュロを取って 1 から 2n − 1 の間の値にしたもの), (1) チーム対 {2n, t} の試合の会場は, t が奇数ならば 2n, t が偶数ならば t の本拠地とし, (2) チーム対 {t + k, t − k} の試合の会場は, k が奇数ならば t − k, k が偶数ならば t + k の本拠地とする.

上記の手続きで作られた実行可能スケジュールを, 本稿では基準スケジュールと呼ぶ. このスケジュールを Kirkman スケジュールと呼ぶ事もあり, 上記の方法は polygon method, circle method と呼ばれる事もあるが, 試合会場までは定めないものを指すこともあり, それぞれが指すものは研究者によって異なることがある.

3 タイムテーブルの作成

スケジュールに対し, それから試合会場の情報を取り除いたものを, 本稿ではタイムテーブルと呼ぶことにする. 本節では, 一重総当り戦のタイムテーブルに対する既存の結果についてまとめる.

タイムテーブルの要素の一部が分かっている (固定されている) とき, 残りの要素を埋めてタイムテーブルを完成する問題を, タイムテーブル完成問題と呼ぶ. タイムテーブル完成問題は, NP 完全であることが知られている [5]. 固定されていない部分が３スロットに限定されていても, NP 完全である. タイムテーブル完成問題は, 部分ラテン方格完成問題と関連している. 部分ラテン方格完成問題の困難性については, 古くは [5,6] の結果が知られているが, 近年 Easton, Parker [8] によって, 様々なバリエーションの NP 完全性が示された. また, チーム i と j の戦いはスロット k で行ってはいけないという, 禁止集合 (i, j, k) ∈ P ⊆ T^{2} × S が与えられたとき, P で与えられる禁止制約を守るタイムテーブルの存在判定問題も, NP 完全であることが知られている [30].

逆に, スロットのうちいくつかを巧妙に埋めて, タイムテーブルを完成することができないようにするには, 何スロットを埋めれば良いかについて, Rosa, Wallis [27] は以下の結果を得ている. チーム数が 8 以上ならば, ３スロット内の試合を (明らかに不能なものを除いて) どのように組んでも, 残りのスロットを埋めてタイムテーブルを完成することができる. 逆に, n スロットの埋め方で, タイムテーブルを完成できないものが存在する. タイムテーブルを完成できないスロットの埋め方を premature set と呼ぶが, n スロットより小さな premature set が存在するかという問題については, 未解決である.

最後に, carry-over effect について紹介する. ラグビーやアメリカンフットボールなどのハードなスポーツのスケジュール作成を考えよう. いま, リーグ戦に参加している 2n チームのうちチーム 2 は非常に強く, チーム 2 と対戦したチームには疲労が残り, その次の試合に影響が残ると想定する. そのような場合, 図 3 と図 4 ではどちらが良いスケジュールだろうか？図 3 のスケジュールでは, チーム 1 が行う 7 試合のうち実に 5 試合で, 「対戦相手の, 直前の対戦相手がチーム 2」になっている. したがって, チーム 1 は相対的に有利になると考えられる. 以下では, このような観点のもとでチーム間の公平性を評価する尺度を紹介する.

リーグ戦のスケジュールにおいて, d 日目にチーム i 対チーム k の試合があり, d + 1 日目 (2n 日目は 1 日目とする) にチーム j 対チーム k の試合が行われるとき, 「チーム i がチーム j に carry-over effect(以下 coe) を与える」と定義する. 与えられたスケジュールに対して, c_{ij} をチーム i がチーム j へ coe を与えた回数とし, これによって定まる行列 C = (c_{ij}) をそのスケジュールに対応する coe 行列と呼ぶ. 定義より, coe 行列はチーム数 2n のスケジュールに対して各行, 各列の和が 2n − 1, 対角要素が 0 の非負整数行列となる. スケジュールに対応する coe 行列 C = (c_{ij}) に対して, ∑_{i,j}(c_{ij}^{2}) をそのスケジュールの coe 値と呼ぶ. 明らかに, coe 値は coe 行列の非対角要素が全て 1 になるとき最小値 2n(2n − 1) をとる.

あるスケジュールから定まる coe 行列の非対角要素が全て 1 になるとき, そのスケジュールを balanced スケジュールという. balanced スケジュールは, 各チームが受け取る coe の発生源が偏っていない, という意味で最適なスケジュールである. 図 4 のスケジュールは balanced スケジュールであり, coe 値は 2n(2n−1) = 56 となる. それに対して図 3 のスケジュールの coe 値は 140 となり, 図 4 のスケジュールと比較して不公平なことがわかる.

coe 値最小化問題は, coe 値を最小にするスケジュールを求める問題である. Russell [29] は, チーム数 2n が 2n = 2^{m} (m ≥ 2) の場合, balanced スケジュールの作成方法を与えた. また同じ論文の中で, チーム数

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 6 日目 7 日目
1  8  3  4  5  6  7  2
2  3  4  5  6  7  8  1
3  2  1  6  8  5  4  7
4  5  2  1  7  8  3  6
5  4  7  2  1  3  6  8
6  7  8  3  2  1  5  4
7  6  5  8  4  2  1  3
8  1  6  7  3  4  2  5

図 3: coe 値 140 のスケジュール

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 6 日目 7 日目
1  4  5  6  7  8  2  3
2  5  4  8  3  6  1  7
3  8  6  5  2  4  7  1
4  1  2  7  6  3  5  8
5  2  1  3  8  7  4  6
6  7  3  1  4  2  8  5
7  6  8  4  1  5  3  2
8  3  7  2  5  1  6  4

図 4: balanced スケジュール (coe 値 56)

表 1: coe 値最小化問題の記録

チーム数 2n 2n(2n − 1) COE 値参考
4  12 12 [29]  balanced
6  30 60 [29]  最適
8  56 56 [29]  balanced
10  90 138 [29], 122 [35], 108 [22]
12  132 196 [29], 188 [13], 176 [22]
14  182 260 [29], 254 [22]
16 240 240 [29] balanced
18  306 428 [29], 400 [22]
20  380 520 [29], 488 [22]

2n = p^{m} + 1 (p は奇素数) の場合に対する発見的解法を提案していた. しかし近年の研究で, この発見的解法はチーム数 6 の場合最適解を与えるが, チーム数 10, 12 の場合にはそうでないことが示された. Russell の発見的解法では, チーム数 10, 12 の場合に得られるスケジュールの coe 値はそれぞれ 138, 196 だったが, チーム数 10 の場合 122(論文 [35]), チーム数 12 の場合には 188(論文 [13]) のスケジュールが発表されている (表 1). これらの結果は制約論理法をベースにした実験で得られたものであり, これ以上のチーム数に対しては計算が難しい. 最新の結果としては, Miyashiro, Matsui [22] によって, 基準スケジュールのスロットを置換する等の手法で, 非常に短い計算時間で従来の結果を更新するスケジュールが発見されている. coe 値の最小化を行う効率的なアルゴリズムは知られておらず, チーム数が 2 のベキ乗でない場合には balanced スケジュールが存在しないだろうと予想されているが, この問題も未解決である.

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 1  3  4  5  6  2 2  5  6  4  3  1 3  1  5  6  2  4 4  6  1  2  5  3 5  2  3  1  4  6 6  4  2  3  1  5 図 5: チーム数 6 のスケジュール (開催場所の割当無し)

4 ブレーク最小化/最大化問題と総移動回数最小化問題

図 1 のスケジュールは, 各チームがそれぞれの日において「どのチームと」「どちらの本拠地で」対戦するか, という情報から成り立っている. 本節では, あらかじめ「どのチームと対戦するか」が決められている場合について考える. 本節で記されている結果の詳細については, 包括的な議論を行っている論文 [34] を参考にされたい.

図 5 のような, 試合開催場所の割当が決定されていないタイムテーブルが与えられた場合, スケジュールを完成させるためには各試合の開催場所 (ホーム／アウェイ) を割り当てる必要がある. タイムテーブル T は, 行と列がそれぞれチーム集合 T とスロット集合 S でインデックスされた行列で, 各要素 τ(t, s) ((t, s) ∈ T ×S) はチーム t のスロット s での対戦相手を表すものである. すなわち, タイムテーブル T は以下の性質:

• 各チーム t ∈ T に対し, タイムテーブル T の第 t 行は, T \ {t} の要素を丁度一つずつ含む;

• 任意の (t, s) ∈ T × S において, τ(τ(t, s), s) = t が成り立つ.

を満たすものである. ホームアウェイ割当 (HA-割当) A とは, 行と列がそれぞれチーム集合 T とスロット集合 S でインデックスされた行列で, 各要素 a_{t,s} ((t, s) ∈ T × S) は H または A となっているものである, ここで a_{t,s} =H ならばチーム t はスロット s でホームゲームを戦うことを意味し, A ならばアウェイゲームを意味する. タイムテーブル T と HA-割当 A が与えられたとき, 任意の ∀(t, s) ∈ T × S について, {a_{t,s}, a_{τ(t,s),s}} = {A, H} が成り立つとき, A と T は整合性を持つと言う. また, 何らかのタイムテーブルと整合性を持つような HA-割当は実行可能であると言う.

さて, ホーム／アウェイを決定する際に, 何を基準にしたらよいだろうか. スポーツスケジューリングの分野では, チーム t が d − 1 日目と d 日目に連続してホームゲームを行う, あるいは連続してアウェイゲームを行うとき, チーム t は d 日目にブレークを持つ, と呼ばれる. 正確には HA-割当 A = (a_{t,s}) ((t, s) ∈ T × S) において, a_{t,s−1} = a_{t,s} = A または a_{t,s−1} = a_{t,s} = H が成り立っているときチーム t はスロット s でブレークを持つと言う. 例えば図 1 のスケジュールでは, ブレークが 6 つある. (図 1 中の下線部がブレークに対応.) ブレークの多いスケジュールは, チーム間の公平性が保たれない, 各本拠地での試合開催間隔がばらばらになる, などの問題点があり, 多くのスポーツ競技において望ましくないスケジュールとされている. ちなみに, 任意の実行可能な HA-割当において, A の連続からなるブレークと H の連続からなるブレークは, 各スロットにおいて同じ数存在することが簡単に分かる. 以下本稿では, HA-割当 A に対するブレーク数を b(A) と表す

もう一つの基準として, 移動回数を考慮するものがある. スケジュールが与えらたとき, 各チームは自らのホームから出発し, スケジュールで指定される試合場を巡り, 全ての試合が終了したら自らのホームに再び戻るとする. このとき試合場を移動する回数を, 全てのチームについて総和をとったものを, 総移動回数とする. (注: 移動が行われないのは, ホームゲームを連続して戦ったときであり, それ以外は移動をすると考える.) 正確には, HA-割当 A = (a_{t,s}) に対する総移動回数 w(A) は

w(A) = ∑_{t∈T} (δ(a_{t,1}) + δ(a_{t,2n−1}) + ∑_{s=1}^{2n−2}(1 − (1 − δ(a_{t,s}))(1 − δ(a_{t,s+1}))))

と表される, ただし δ(A) = 1, δ(H) = 0 である. メジャースポーツのリーグ戦においては, 上記のような移動は非現実的であると思われるが, 例えばアメリカ野球マイナーリーグについて扱っている論文 [28] では, 各チームが上記のような移動を行っており, スケジュール作成においてはブレーク数は全く考慮されていないことが言及されている.

実は, ブレーク最小化と総移動回数最小化は相反する目的であることが以下の性質から導かれる.

補題 1 [37] チーム数 2n の実行可能な HA-割当 A について, w(A) + (1/2)b(A) = 2n(2n − 1) が成り立つ.

上記より, 総移動回数を最小化する HA-割当は, ブレーク数を最大化する HA-割当となっており, その逆も成り立つことが分かる.

Miyashiro, Matsui [20] は, ブレーク最小化と最大化の 2 つの問題が本質的に等価であることを導く以下の性質を示している. 与えられた HA-割当 A = (a_{t,s}) ((t, s) ∈ T × S) に対し, 新たな HA-割当 Ã = (ã_{t,s}) ((t, s) ∈ T × S) を以下のように定義する:

• ∀s = 1, 3, …, 2n − 1, ã_{t,s} := a_{t,s} (∀t ∈ T);

• ∀s = 2, 4, …, 2n − 2, if a_{t,s} = H then ã_{t,s} := A, else ã_{t,s} := H (∀t ∈ T).

定義より明らかに, A がタイムテーブル T と整合性を持つならば, Ã もまた T と整合性を持つ. HA-割当 Ã の定義より, 以下が簡単に導かれる.

補題 2 [20] チーム数 2n の実行可能な HA-割当 A について, b(A) + b(Ã) = 4n(n − 1) が成り立つ.

上記 2 つの補題より, 以下が導かれる.

定理 3 与えられたタイムテーブル T について, T と整合性を持つ HA-割当に関する以下の性質は全て等価である:

(1) A は総移動回数 w(A) を最小化する,

(2) A はブレーク数 b(A) を最大化する,

(3) Ã はブレーク数 b(Ã) を最小化する.

ブレーク最小化問題は NP-困難と予想されているが [10] まだ解決はされていない. 上記定理から明らかなように, ブレーク最小化問題, ブレーク最大化問題, 総移動回数最小化問題の 3 つは本質的に等価であり, どれか一つが NP-困難ならばすべて NP-困難であり, どれか一つが多項式時間で解ければすべて多項式時間で解ける.

残念ながら, (チーム数が偶数の際は) ブレークの無いスケジュールは存在しないが, ブレーク数の下界が知られており, これより以下のようなブレーク数の上界及び総移動回数の下界が得られる;

定理 4 [7, 20, 37] チーム数 2n の実行可能な HA-割当 A について, 2n − 2 ≤ b(A) ≤ (2n − 1)(2n − 2), w(A) ≥ (2n − 1)(n + 1) が成り立つ.

証明: 任意の実行可能スケジュールにおいて, 対応する HAT 中のある 2 つの行が同じになることは無い. なぜならば, もしこのような行の対 (チーム対) が存在するならば, このチーム対が戦う試合が存在しないからである. ブレークが存在しないチームの HAT における行は, A と H が交互に現れるものであり, 2 種類しか存在しない. ゆえにブレークが存在しないチームは, 最大 2 つしか存在しない. よってブレークの総数は, 2n−2 以上である.

ブレーク数の下界 2n−2 ≤ b(Ã) より, b(A) = 2n(2n−2)−b(Ã) ≤ 2n(2n−2)−(2n−2) = (2n−1)(2n−2) と w(A) = 2n(2n − 1) − (1/2)b(A) ≥ 2n(2n − 1) − (1/2)(2n − 1)(2n − 2) = (2n − 1)(n + 1) が得られる. ■

基準スケジュールはブレーク数が 2n − 2 となっており, 上記の下界は最も良いものとなっていることが分かる. 基準スケジュールにおいて, 第 1 日目の試合全てを, 第 2n − 1 日目の後に移動することにより, 各チームがブレークの試合を丁度 1 つ持つ実行可能スケジュールを作ることができる. ブレーク数最小のスケジュールは, ブレークの無いチームが出現することから, 不公平であるとされることも多く, 「各チームが丁度 1 回ブレークを持つスケジュール」が好まれることもある [7]. チーム数が 2n − 1 のときは, チーム数 2n の基準スケジュールにおいて, チーム 2n を架空のチームとし, チーム 2n との戦いは対戦チームの休みに対応させると, ブレークの存在しないスケジュールとなる.

任意のタイムテーブルについて, 以下のことが成り立つことも知られている.

定理 5 [20] 任意のタイムテーブル T について, T と整合性を持つ HA-割当 A で b(A) ≥ 3n(n − 1), b(Ã) ≤ n(n − 1), w(A) ≤ (1/2)n(5n − 1) を満たすものが存在する.

上記のような HA-割当は多項式時間で生成することが可能であり, この手続きは (1) ブレーク最大化問題に対する (3/4) 近似解法, (2) 総移動回数最小化問題に対する (5/4) 近似解法になっている [34].

4.1 ブレーク最小化問題

ブレーク最小化問題に対しては, 1998 年に Régin [24] が制約論理法を用いてチーム数 20 までのインスタンスを, 2000 年には Trick [35] が整数計画法を用いた定式化を行いチーム数 22 までのインスタンスを解いている. 2003 年には Elf, Jünger, Rinaldi [10] がグラフ上の MAX CUT を求める問題として定式化を行い, 専用の分枝限定法を実装してチーム数 26 までのインスタンスを現実的な時間で解いた. Miyashiro, Matsui [21] は, ブレーク最小化問題を MAX RES CUT および MAX 2SAT として定式化し, Goemans, Williamson [11] の SDP 緩和を用いた近似解法を適用して, 大規模なインスタンス (〜40 チーム) に対しても高速に質の良いスケジュールが生成できることを実証した. 一方 Elf ら [10] は, 「チーム数 2n のブレーク最小化問題において, ブレークが 2n − 2 となるような HA-割当が存在するか否かは多項式時間で判定可能」という予想を提出していたが, これは Miyashiro, Matsui [20] によって肯定的に解決された. 論文 [20] では, 上記の判定問題を 2n 個の 2SAT 問題を解く事に帰着し, O(n^{3}) 時間の算法を提案している.

4.2 ブレーク最大化問題

ブレーク最大化問題は [9, 20, 28, 37] 等の論文で議論されている. 以下では, ブレーク最大化問題が UN-WEIGHTED MAX RES CUT(問題) に変形される事を記す. まず最初に, UNWEIGHTED MAX RES CUT(問題) を定義する. 頂点集合 V と無向枝集合 E からなる無向グラフを G = (V, E) とする. 任意の頂点部分集合 V′ ⊆ V に対し, δ(V′) = {{v_{i}, v_{j}} : v_{i}, v_{j} ∈ V, v_{i} ∉ V′ ∋ v_{j}} と定義する. 無向グラフ G = (V, E) と頂点対の集合 E_{cut} ⊆ {X ⊆ V : |X| = 2} が与えられたとき, UNWEIGHTED MAX RES CUT は, E_{cut} ⊆ δ(V′) を満たす頂点部分集合 V′ で |δ(V′) ∩ E| を最大化するものを見つける問題である.

タイムテーブル T = (τ(t, s)) ((t, s) ∈ T × S) が与えられたとき, 無向グラフ G = (V, E) を以下のように構築する: 頂点集合を V = {v_{t,s} : (t, s) ∈ T × S} とし, 無向枝集合を E = {{v_{τ(t,s−1),s−1}, v_{t,s}} : t ∈ T, s ∈ S \ {1}} とする. 更に, 頂点対集合 E_{cut} = {{v_{t,s}, v_{τ(t,s),s}} : (t, s) ∈ T × S} を構築する. 上記の G と E_{cut} で定義される UNWEIGHTED MAX RES CUT の任意の許容解 V′ に対して (すなわち V′ は E_{cut} ⊆ δ(V′) を満たしている), HA-割当 A′ = (a′_{t,s}) ((t, s) ∈ T × S) を以下のように定める: もし v_{t,s} ∈ V′ ならば a′_{t,s} = A とし, それ以外は a′_{t,s} = H とする. 明らかに A′ と T は整合性を持つ. 任意のタイムテーブル T に対し, 対応する UNEWEIGHTED MAX RES CUT 問題の許容解集合と, T と整合性を持つ HA-割当の集合の間には全単写が存在するのは明らかであろう. また (t, s) ∈ T × S \ {1} において, a′_{t,s−1} = a′_{t,s} となる必要十分条件は {v_{τ(t,s−1),s−1}, v_{t,s}} ∈ δ(V′) が成り立つことである. ゆえに |δ(V′) ∩ E| = b(A′) が成立し, ブレーク最大化問題は UNWEIGHTED MAX RES CUT に変形される. (UNWEIGHTED) MAX RES CUT に対し Goemans, Williamson [11] は, 半正定値緩和に基づく 0.878-近似解法を提案しているが, 上記の変形よりこの解法はブレーク最大化問題に対する 0.878-近似解法になっていることが分かる.

4.3 総移動回数最小化問題

以下では, 総移動回数最小化問題を MIN 2SAT(問題) に変形する手続きについて記す. MIN 2SAT(問題) は, 最大 2 個のリテラルからなるクローズの集合が与えられたとき, 真となるクローズの個数を最小にする真偽割当を見つける問題である. タイムテーブル T = (τ(t, s)) ((t, s) ∈ T × S) が与えられたとする. まず最初に (基本) 論理変数 Y_{t,s} ((t, s) ∈ T × S) を導入し, Y_{t,s} はチーム t がスロット s でアウェイゲームを戦うとき TRUE の値を持つとする. するとチーム t のスロット s と s + 1 の間での移動回数が 1 となるのはクローズ Y_{t,s} ∨ Y_{t,s+1} が TRUE となる時であり, またその時に限る. 同様にして, チーム t の第 1 スロット直前 (あるいは最終スロット直後) の移動回数が 1 となる必要十分条件は, 変数 Y_{t,1} (あるいは Y_{t,2n−1}) の値が TRUE となる事である. 上記で導入された論理変数の真偽割当に対する HA-割当が, 与えられたタイムテーブル T = (τ(t, s)) と整合性を持つ必要十分条件は, 任意の (t, s) ∈ T × S において論理変数 Y_{t,s} が論理変数 Y_{τ(t,s),s} の否定となっている事である. 以上より, 総移動回数最小化問題を MIN 2SAT に変形することができる. Bertsimas ら [4] は, MIN kSAT に対する近似解法で, 近似率が 2(1 − (1/2)^{k}) となるものを提案している. これを用いると総移動回数最小化問題に対する (3/2)-近似解法となる. また Avidor, Zwick [2] は, 半正定値緩和に基づく MIN 2SAT の 1.1037-近似解法を提案している. Suzuka らは [32,33] において計算実験を行い, [34] において包括的な議論を行っている.

5 会場割当問題

会場割当問題とは, タイムテーブルと距離行列が与えられたとき, 総移動距離を最小にする HA-割当を見つける問題である. ただし, 距離行列 D とは, 行と列がそれぞれ T でインデックスされた対称行列である. 距離行列の (i, j) 要素である d(i, j) はチーム i の本拠地から j の本拠地までの距離を表す. 本稿で取り扱う距離関数は, 三角不等式を満たしていると仮定する. チーム t の移動距離は, タイムテーブルと HA-割当と距離行列が与えられたとき, t のホームを出発し, タイムテーブルと HA-割当に従って対戦会場を訪問し, 最後に t のホームに戻ってくる経路の長さと定義され, 総移動距離とは, 各チームの移動距離の総和である. 各本拠地間の距離がすべて 1 のとき, 会場割当問題は総移動回数最小化問題と一致する.

Suzuka ら [33, 34] によって提案されたを 0-1 線形整数計画問題に基づく方法について簡単に記す. 以下では最終スロットを ŝ と表す, すなわち ŝ = 2n − 1 である. まず 0-1 変数 y_{t,s} ((t, s) ∈ T × S) を導入し, チーム t がスロット s でアウェイゲームを戦うとき, 変数 y_{t,s} は 1 の値をとるとする. 更に連続変数 w_{t,s} ((t, s) ∈ T × S \ {ŝ}) を導入し, w_{t,s} はチーム t のスロット s と s + 1 の間の移動距離を表すとする. このとき会場割当問題は以下のように定式化される:

(IP)

min. ∑_{t∈T} ( ∑_{s∈{1,ŝ}} d(t, τ(t, s)) y_{t,s} + ∑_{s∈S\{ŝ}} w_{t,s})

s. t. w_{t,s} ≥ d(t′, t) y_{t,s} + (d(t′, t′′) − d(t′, t)) y_{t,s+1} ( \begin{matrix}∀(t, s) ∈ T × S \ \{ŝ\}, where \\ t′ = τ(t, s) and t′′ = τ(t, s + 1)) \end{matrix} ) ,

w_{t,s} ≥ (d(t′, t′′) − d(t, t′′)) y_{t,s} + d(t, t′′) y_{t,s+1} ( \begin{matrix}∀(t, s) ∈ T × S \ \{ŝ\}, where \\ t′ = τ(t, s) and t′′ = τ(t, s + 1)) \end{matrix} ) ,

y_{t,s} + y_{τ(t,s),s} = 1  (∀(t, s) ∈ T × S),
y_{t,s} ∈ {0, 1}  (∀(t, s) ∈ T × S),

ここで w_{t,s} ((t, s) ∈ T × S \ {ŝ}) は連続変数であることに注意されたい. 問題 IP の整数制約を非負制約 y_{t,s} ≥ 0 (∀(t, s) ∈ T × S) に置き換えて得られる線形緩和問題の最適解は半整数性を持つ事が証明できる

定理 6 [33,34] 距離行列 D は, 対称であり三角不等式を満たすとする. このとき問題 IP の線形緩和問題の任意の最適端点解は, ∀(t, s) ∈ T × S, y_{t,s} ∈ \{0, \frac{1}{2}, 1\} を満たす.

総移動回数最小化問題について, 問題 IP の線形緩和問題を解いた際は, 以下が成り立つ;

補題 7 [34] 総移動回数最小化問題 (すなわち距離行列 D の非対角要素が全て 1) の場合, 問題 IP の線形緩和問題は唯一の最適解 (y^{∗}, w^{∗}) ただし y_{t,s}^{∗} = 1/2 (∀(t, s) ∈ T × S) かつ w_{t,s}^{∗} = 1/2 (∀(t, s) ∈ T × S \ {ŝ}) を持つ.

論文 [33] では, 問題 IP の線形緩和問題を解き, 最適解が整数解でない場合, 以下のように 0 または 1 に丸める解法を提案している. 以降では, IP の線形緩和問題の最適解における変数 y_{t,s} の値を y_{t,s}^{∗} と表記する. 以下の A1–A3 は [33] で提案されている操作である.

A1: 各 0-1 変数の組 (y_{t,s}, y_{τ(t,s),s}) について独立に, 確率 y_{t,s}^{∗} で (1,0), 確率 1 − y_{t,s}^{∗} で (0,1) とする. A2: 各 0-1 変数の組 (y_{t,s}, y_{τ(t,s),s}) を等確率で (1,0) または (0,1) とした初期解 y′ を作成する. 次に [0,1)

上の一様分布に従った確率変数 U を (1 つだけ) 生成し, 各変数 y_{t,s} について「y′_{t,s} = 1 かつ y_{t,s}^{∗} ≥ U」または「y′_{t,s} = 0 かつ y_{t,s}^{∗} < U」のとき 1 とする (1 でないものは 0 とする). ここで全ての変数に対し, 同一の U を用いる事に注意されたい.

A3: A2 の初期解に, 定理 5 におけるブレーク数 3n(n − 1) 以上の HA-割当に対応する 0-1 解を用いる. 定理 6 で示した様に, 線形緩和問題の最適解として半整数性を満たすものがあることから, 最適解としてこれを用いると, 1 でも 0 でも無い変数は全て (1/2) の値を持ち, この性質を用いると上記の解法の実現は非常に容易となる [33].

次に論文 [21,32,34] 等で提案されている, MIN RES CUT 問題への変形について記す. まず最初に, MIN RES CUT(問題) を定義する. 頂点集合 V と無向枝集合 E からなる無向グラフを G = (V, E) とする. 任意の頂点部分集合 V′ ⊆ V に対し, δ(V′) = {{v_{i}, v_{j}} : v_{i}, v_{j} ∈ V, v_{i} ∉ V′ ∋ v_{j}} と定義する. 無向グラフ G = (V, E) と頂点対の集合 E_{cut} ⊆ {X ⊆ V : |X| = 2}, 頂点 r ∈ V, 枝重み ℓ : E → R が与えられたとき, MIN RES CUT は, E_{cut} ⊆ δ(V′) と r ∉ V′ を満たす頂点部分集合 V′ で ∑_{e∈δ(V′)∩E} ℓ(e) を最小化するものを見つける問題である. この問題において, 制約 r ∉ V′ は冗長であるが, この後の問題変形において有用なため導入されている.

次に会場割当問題を MIN RES CUT に変形する. 与えられたタイムテーブル T = (τ(t, s)) ((t, s) ∈ T ×S) に対し, 無向グラフ G = (V, E) を以下のように定義する. まず人工的な頂点 r を導入し, V = {v_{t,s} : (t, s) ∈ T × S} ∪ {r}, E = {{v_{t,s−1}, v_{t,s}} : t ∈ T, s ∈ S \ {1}} ∪ {{r, v_{t,s}} : (t, s) ∈ T × S} とし, E_{cut} = {{v_{t,s}, v_{τ(t,s),s}} : (t, s) ∈ T × S} と定義する. このように定義された MIN RES CUT の問題例に対し, 任意の許容解 V′ (すなわち r ∉ V′ と E_{cut} ⊆ δ(V′) を満たす頂点部分集合 V′ ⊆ V) から, HA-割当 A = (a_{t,s}) ((t, s) ∈ T × S) を以下のように作る: もし v_{t,s} ∈ V′ ならば a_{t,s} = A とし, それ以外は a_{t,s} = H とする. この HA-割当が T と整合性を持つのは明らかである. また明らかに, 任意の HA-割当に対して, MIN RES CUT の許容解で対応するものが唯一存在する. 次に総移動距離について議論する. タイムテーブル T と距離行列 D = (d(i, j)) の対が与えられたとき, 枝長さ ℓ : E → R_{+} を

ℓ(\{v_{t,s}, r\}) = \frac{d(t′, t′′) − d(t, t′′) + d(t′, t)}{2}

+\frac{d(τ(t, s − 1), t′) + d(t, t′) − d(τ(t, s − 1), t)}{2} (∀t ∈ T, ∀s ∈ S \ \{1, ŝ\}),

ℓ(\{v_{t,1}, r\}) = d(t, τ(t, 1)) + \frac{d(τ(t, 1), τ(t, 2)) − d(t, τ(t, 2)) + d(τ(t, 1), t)}{2},
ℓ(\{v_{t,ŝ}, r\}) = d(τ(t, ŝ), t) + \frac{d(τ(t, ŝ − 1), τ(t, ŝ)))}{2} + \frac{d(t, τ(t, ŝ)) − d(τ(t, ŝ − 1), t)}{2},
ℓ(\{v_{t,s}, v_{t,s+1}\}) = \frac{−d(t′, t′′) + d(t, t′′) + d(t′, t)}{2} (∀t ∈ T, ∀s ∈ S \ \{ŝ\}).

と定義すると, 総移動距離は MIN RES CUT の目的関数値に等しくなる [32, 34], ただし上記において t′ = τ(t, s), t′′ = τ(t, s + 1) である.

MIN RES CUT の最大化版である MAX RES CUT に対し, Goemans, Williamson [11] は 0.878-近似解法を提案している. MIN RES CUT の制約は MAX RES CUT の制約と同じ構造を持つことから, [11] と同様の手法が適用できる. (ただし, 最小化問題であるため, 得られた解の近似比率を [11] と同じ手法で理論的に保証することはできない.)

最後に, Suzuka らによる計算実験結果 [33, 34] について簡単に報告する. 表 2,3,4,5 に, チーム数 2n = 16, 18, 20, 22, 24, 26, 30, 40 に対しそれぞれ 10 題ずつ解いた実験結果の概要を示す. 表から分かるように, 会場割当問題については, 整数計画問題 IP の線形緩和問題の最適解において, 殆どの変数が 0 または 1 の値をとっており, 多くの問題において整数解が得られている. これに対し総移動回数最小化問題においては, Goemans, Williamson [11] に基づく解法が質の良い解を生成している.

6 HAT 許容性判定問題

本節では, ブレーク最小化問題とは逆に, 条件として各試合のホーム／アウェイのみが先に固定された状況を考える. 実際のスケジューリング現場では, 試合開催場所の確保の観点などから, 各試合がホーム／アウェイのどちらで行われるかが前もって決められている場合も多い. 図 6 は各試合がホームもしくはアウェイのどちらで行われるかを指定している. (H がホーム, A がアウェイに対応.)

HA-割当が制約条件として与えられた場合, スケジュール作成者はそれに従いタイムテーブルを作成していく. (図 6 から作成できるタイムテーブルのうちのひとつが, 図 1 である.) しかし, 任意の HA-割当からタイムテーブルが作成できるわけではなく, HA-割当によってはそれが不可能なことがある. タイムテーブルを作成できる HA-割当の必要条件として,

チーム 1 日目 2 日目 3 日目 4 日目 5 日目
1  H  A  H  A  H
2  A  H  \underline{H}  \underline{H}  A
3  A  H  A  \underline{A}  H
4  A  H  A  H  A
5  H  A  \underline{A}  \underline{A}  H
6  H  A  H  \underline{H}  A

図 6: チーム数 6 の HA-割当

チーム 1 日目 2 日目 3 日目 4 日目 5 日目
1  H  A  \underline{A}  H  A
2  H  A  H  \underline{H}  A
3  H  A  H  A  \underline{A}
4  A  H  \underline{H}  A  H
5  A  H  A  \underline{A}  H
6  A  H  A  H  \underline{H}

図 7: スケジュール生成不可能な HA-割当

• それぞれのスロットについて, H と A の数が同数

• H と A のパターンが全く同じチーム (行) が存在しない

というものがあるが, この条件を満たす HA-割当が全てタイムテーブルを生成可能というわけではない. 図 7 は, 上記の条件を満たしているがタイムテーブルの生成ができない HA-割当の一例である.

与えられた HA-割当がタイムテーブルを生成できるか否か (HA-割当の許容性) を判定する問題が, HAT 許容性判定問題である (HA-割当の行列を Home-Away Table とも呼ぶことから, この問題は Home-Away Table feasibility と呼ばれるため, 本節では HAT 許容性判定問題と記す). この問題は, 既に 1980 年の de Werra の論文 [7] において未解決問題として提起されている. また, Nemhauser, Trick [23] の論文においても注目するべき問題として触れられており, スポーツスケジューリングの大きな未解決問題の一つである. しかしこれまで, この問題に対する多項式時間アルゴリズム, NP-完全性の証明, 実行可能 HA-割当 (タイムテーブルを生成できる HA-割当) の特徴付けのいずれも得られていない.

以下では Miyashiro ら [19] によって提案された必要条件について記す. 以下では HA-割当 A が与えられているとする. チームの部分集合 T′ ⊆ T とスロット s ∈ S に対し, (所与の HA-割当 A の下で) スロット s においてアウェイゲームを戦っている T′ 中のチーム数を A(T′, s) とする. 同様にホームゲームについて H(T′, s) を定義する. 関数 α を

α(T′) = ∑_{s∈S} min{A(T′, s), H(T′, s)} − (1/2)|T′|(|T′| − 1)

と定義すると, 以下が成り立つ.

補題 8 [19] 任意の実行可能 (許容)HA-割当について, ∀T′ ⊆ T, α(T′) ≥ 0 が成り立つ.

上記より, α(T′) < 0 を満たすチームの部分集合 T′ が存在するならば, 与えられた HA-割当は実行可能ではない. しかしながら, 上記の不等式は 2^{2n} − 1 本あり, これら全てを逐次確認するのは指数時間の手間が必要チーム

1 HHHHAAAAHAAAH
2 HHHHAAAAHHAAA
3 HHHHAAAAAHHAA
4 HHHHAAAAAAHHA
5 HHHHAAAAAAAHH
6 HHHHHHHHAAAAH
7 AAAAHHHHHAAAH
8 AAAAHHHHHHAAA
9 AAAAHHHHAHHAA
10 AAAAHHHHAAHHA
11 AAAAHHHHAAAHH
12 HHAAHAAAHHHHH
13 AAHAAHAAHHHHA
14 AAAHAAHHHHHHH

図 8: 柏原による 14 チームの実行不能 HA-割当

となる. さらに残念ながら一般の HA-割当については, 条件 [∀T′ ⊆ T, α(T′) ≥ 0] は十分条件ではない事が柏原 [14] によって示されている. 柏原によって作られた, 上記の条件を満たす実行不能スケジュールを図 8 に示す.

しかしながら Miyashiro らの論文 [19] では, 各チームがブレークを高々1 個しか持たないような HA-割当に関しては, 与えられた HA-割当が条件 [∀T′ ⊆ T, α(T′) ≥ 0] を満たしているかを O(n^{4}) で判定でき, 更にチーム数が 26 以下の場合は, この条件が HA-割当が実行可能であることの必要十分条件となっていることを, 計算機実験によって確かめている. 以上より次の性質が予想されている.

予想 1 [19] 与えられた HA-割当において, 各チームがブレークを高々1 個しか持たないとする. このとき, [∀T′ ⊆ T, α(T′) ≥ 0] は, 与えられた HA-割当が実行可能である必要十分条件である.

現状では HAT 許容性判定問題は整数計画法 [23] や制約論理法 [13] を用いて解かれることが多いが, これらの方法ではチーム数が多くなると計算時間が増大する.

7 巡回トーナメント問題

「各チームがそれぞれ異なる本拠地を持ち, 各試合は対戦するチームのどちらかの本拠地で行う」というリーグ戦の形式は, 野球, サッカーなどをはじめとするプロのスポーツ競技で広く用いられている. このとき, リーグ戦のスケジュールをうまく作成することにより各チームの移動距離の総和を最小化する問題が巡回トーナメント問題である. 国土が広大な国では, 移動距離を減少させることによる移動コストの削減効果は非常に大きくなる. 最近では, Ribeiro, Urrutia [25] が, メタ・ヒューリスティクスを用いてブラジルのプロサッカーリーグ (2003 年, 24 チーム) の移動距離最小化をはかり, 費用にして約 270 万ドルの削減に成功した. 彼らの作成したスケジュールの総移動距離は 55 万 km だったが, 同時にスケジュール委員会が手作業で作成したスケジュールの移動距離は約 150 万 km だったと報告されている.

巡回トーナメント問題は, 対象とするそれぞれのスポーツ競技によって条件が異なるが, ベンチマークとして “Traveling Tournament Problem”(以下 TTP) がよく知られている. TTP のベンチマークデータは, Trick による Web ページ [36] に公開されている. 与えられる制約条件により, 問題にいくつかの種類があるが, 最も良く研究されているのは以下のような問題である. TTP では各チームの持つ本拠地間の距離行列のみが与えられている. このとき, 2 重総当り戦スケジュールで以下を満たすものを対象とする:

(TTP1) 各チームはホームゲームの連続は高々3 回まで,

(TTP2) 各チームはアウェイゲームの連続は高々3 回まで,

(TTP3) 各チーム対は連続して戦わない (i 対 j の試合が行われたスロットの直後のスロットでの j 対 i の試合は禁止). TTP は, (TTP1)〜(TTP3) の制約を満たすスケジュールの中で, チームの移動距離の総和が最小のものを求める問題である. ただし, 各チームは自分の本拠地から出発し, すべての試合が終了したあと自分の本拠地に帰って来るとする. TTP の問題例は適度に抽象化されており他のスポーツスケジューリングにも容易に適用できること, また, 問題の数値データ, 現在までの最良の上界と下界の記録が公開されていることから, この問題に対する研究が一気に広まった.

これまで TTP の上界の記録は, ほとんどメタ・ヒューリスティクスを用いた研究により更新されてきた. 特に, Anagnostopoulos, Michel, Van Hentenryck, Vergados [1] によるシミュレーテッド・アニーリングを用いた手法は, 従来得られていた上界値の記録を大幅に更新した. 現在も TTP の最良暫定解の大部分が彼らによって発見されたものである.

一方, TTP の下界値の更新は進んでいない. TTP は巡回セールスマン問題とよく似た構造を持つが, 同程度の規模の巡回セールスマン問題と比較して最適解を求めるのが極めて困難である. 例えば, 現時点において最適解が求められているのは, チーム数 (たった！ )8 以下の問題例に限られている. この結果は, Easton, Nemhauser, Trick [9] によって, TTP を整数計画問題として定式化し, 20 台の計算機上で並列分枝限定法を 5 日間走らせることにより得られたものであるから, 生半可な結果ではない. これだけからも, TTP がいかに想像できる. チーム数 10 以上のインスタンスに関して, これまでの手法を用いたのでは現実的な時間内に最適性を証明するのは難しく, 研究に何らかのブレークスルーが必要だと考えられる.

TTP の他の変種としては, 論文 [28] において Russe, Leung は, (TTP1)〜(TTP3) の代わりに, (RL1) 各チームはホームゲームの連続は高々2 回まで, (RL2) 各チームはアウェイゲームの連続は高々2 回まで,

とした特殊な 4 重総当り戦について議論している. また, 2005 年に行われた東京工業大学スーパーコンピューターコンテストでは,

(SC1) 各チームはホームゲームの連続は高々2 回まで,

(SC2) 各チームはアウェイゲームの連続は高々3 回まで, という制約の元で, 日本男子プロバレーボールの V リーグ (6 チーム) の本拠地間の距離を元に作成した距離行列に対する 2 重総当り戦スケジュールを作成する問題が, 本戦課題に取り上げられている [17].

8 実際のスケジュール

現実にはどんなスケジュールが使われているか見るため, J リーグとセリエ A において実際に用いられたスケジュールの HA-割当を表 6 に挙げる. J リーグのスケジュールは, ブレーク数の公平性という観点からは, セリエ A のスケジュールより質が悪いことが分かる. (実際は, 各試合日の間に○○杯といった試合が入るため, この表だけから判断を下すことは出来ないかもしれない.)

9 おわりに

本稿では, スポーツスケジューリングにおける最近の研究を中心にして紹介した. 本文中で引用した以外にも, スポーツスケジューリングの適用先はアメフト, 野球, バスケットボール, チェス, クリケット, アイスホッケー, サッカー, テニス, 卓球など, 非常に多岐にわたっている. 現時点でのスポーツスケジューリングは, 計算機の普及と高速化, および各種解法の発達により現実問題への適用が進んでいる. その一方で, スポーツ興行の巨大化にも対応できるさらに高速なアルゴリズムの開発など, 取り組むべき課題は多数残っている. グラフ理論やデザイン理論, 組合せ理論を用いた研究は, 1980 年代に複数行われたが, 近年あまり新しい成果は出ていない. しかしながら最近数年の間に, Traveling Tournament Problem 等の提起によって, 現実的な制約が整理されつつあり, これらの制約の下での carry-over effect 最小化や, ブレーク最小化/最大化問題に対して, 理論からのアプローチが必要となっている.

将来, 日本のスポーツ産業界において数理手法によるスケジューリングが当たり前になるだろうか？今後のスポーツスケジューリングの発展が楽しみである.

参考文献

[1] A. Anagnostopoulos, L. Michel, P. Van Hentenryck, and Y. Vergados, “A simulated annealing approach to the traveling tournament problem,” in: Proceedings of the 5th International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2003 (available at http://www.cs.brown.edu/people/pvh/).

[2] A. Avidor, and U. Zwick, “Approximating MIN k-SAT,” in: Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, 2518 (2002), pp. 465–475.

[3] T. Bartsch, A. Drexl, and S. Kröger, “Scheduling the professional soccer leagues of Austria and Germany,” Computers & Operations Research, 33 (2006), pp. 1907-1937

[4] D. Bertsimas, C. Teo, and R. Vohra, “On dependent randomized rounding algorithms,” Operations Research Letters, 24 (1999), pp. 105–114.

[5] C. Colbourn, “Embedding partial Steiner triple systems is NP-complete,” Journal of Combinatorial Theory A, 35 (1983), pp. 100–105.

[6] C. Colbourn, “The complexity of completing partial Latin squares,” Discrete Applied Mathematics, 8 (1984), pp. 25–30.

[7] D. de Werra, “Geography, games and graphs,” Discrete Applied Mathematics, 2 (1980), pp. 327–337.

[8] T. Easton and R. G. Parker, “On completing Latin squares,” Discrete Applied Mathematics, 113 (2001), pp. 167–181.

[9] K. Easton, G. L. Nemhauser, and M. A. Trick, “Solving the traveling tournament problem: a combined integer programming and constraint programming approach,” Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science, 2740 (2003), Springer, Berlin, pp. 100–109.

[10] M. Elf, M. Jünger, and G. Rinaldi, “Minimizing breaks by maximizing cuts,” Operations Research Letters, 31 (2003), pp. 343–349.

[11] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the ACM, 42 (1995), pp. 1115–1145.

[12] J. L. Gross and J. Yellen (eds.), Handbook of Graph Theory, 2004, CRC Press, Boca Raton, pp. 462–470.

[13] M. Henz, T. Müller, and S. Thiel, “Global constraints for round robin tournament scheduling,” European Journal of Operational Research, 153 (2004), pp. 92–101.

[14] 柏原賢二, 「総当りゲームと 1-factorization」 , 2003 年応用数学合同研究集会報告集, pp. 21–24.

[15] J. Y-T. Leung (ed.), Handbook of Scheduling: algorithms, models, and performance analysis,” 2004, CHAP-MAN & HALL/CRC, Boca Raton, pp. 52-1–52-19.

[16] 松井知己, 「スポーツのスケジューリング」 , オペレーションズ・リサーチ, 44 (1999), pp. 141–146.

[17] 松井知己, 「スーパーコンピューティングコンテスト 2005」 , 数学セミナー, 45 (2006), pp. 58–61.

[18] 宮代隆平, 松井知己, 「1993 年 J リーグの再スケジューリング」 , オペレーションズ・リサーチ, 45 (2000), pp. 81–83.

[19] R. Miyashiro, H. Iwasaki, and T. Matsui, “Characterizing feasible pattern sets with a minimum number of breaks,” in: Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science, 2740 (2003), Springer, Berlin, pp. 78–99.

[20] R. Miyashiro and T. Matsui, “A polynomial-time algorithm to find an equitable home-away assignment,” Operations Research Letters, 33 (2005), pp. 235–241.

[21] R. Miyashiro and T. Matsui, “Semidefinite programming based approaches to the break minimization problem,” Computers & Operations Research, 33 (2006), pp. 1975–1982.

[22] R. Miyashiro and T. Matsui, “Minimizing carry-over effects in a round-robin tournament,” in preparation.

[23] G. L. Nemhauser and M. A. Trick, “Scheduling a major college basketball conference,” Operations Research, 46 (1998), pp. 1–8.

[24] J. -C. Régin, “Minimization of the number of breaks in sports scheduling problems using constraint programming,” in: Constraint Programming and Large Scale Discrete Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 57 (2001), American Mathematical Society, pp. 115–130.

[25] C. C. Ribeiro and S. Urrutia, “OR on the ball: applications in sports scheduling and management,” OR/MS Today, 31 (2004), pp. 50–54.

[26] F. M. Rokosz, Procedures for Structuring and Scheduling Sports Tournaments (3rd Edition), Charles C Thomas Publisher, Illinois, 2000.

[27] A. Rosa and W. Wallis, “Premature sets of 1-factors or how not to schedule round robin tournaments,” Discrete Applied Mathematics, 4 (1982), pp. 217–226.

[28] R. A. Russel and J. M. Y. Leung, “Devising a cost effective schedule for a baseball league,” Operations Research, 42 (1994), pp. 614–625.

[29] K. G. Russell, “Balancing carry-over effects in round robin tournaments,” Biometrika, 67 (1980), pp. 127–131.

[30] A. Schaerf, “Scheduling sport tournaments using constraint logic programming,” Constraints, 4 (1999), pp. 43–65.

[31] J. A. M. Schreuder: “Combinatorial aspects of construction of competition Dutch professional football leagues,” Discrete Applied Mathematics, 35 (1992), pp. 301–312.

[32] A. Suzuka, R. Miyashiro, A. Yoshise, and T. Matsui, “Semidefinite programming based approaches to homeaway assignment problems in sports scheduling,” In: The First International Conference on Algorithmic Applications in Management (AAIM 2005), Lecture Notes in Computer Science, 3521 (2005) pp. 95–103.

[33] A. Suzuka, R. Miyashiro, A. Yoshise, and T. Matsui, “Dependent randomized rounding to the home-away assignment problem in sports scheduling,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (to appear).

[34] A. Suzuka, R. Miyashiro, A. Yoshise, and T. Matsui, “The home-away assignment problems and break minimization/maximization problems in sports scheduling,” Mathematical Engineering Technical Reports, METR 2006-05, Department of Mathematical Informatics, Graduate School of Information Science and Technology, the University of Tokyo, 2006 (available at http://www.keisu.t.u-tokyo.ac.jp/Research/techrep.0.html).

[35] M. A. Trick, “A schedule-then-break approach to sports timetabling,” in: Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Science, 2079 (2001), Springer, Berlin, pp. 242–253.

[36] M. A. Trick, “Challenge traveling tournament instances,” Web Page, since 1999 (http://mat.tepper. cmu.edu/TOURN/).

[37] S. Urrutia and C. C. Ribeiro, “Maximizing breaks and bounding solutions to the mirrored traveling tournament problem,” Discrete Applied Mathematics (to appear).

[38] 読売新聞, 朝刊スポーツ面, 2004 年 11 月 9 日.

表 2: 会場割当問題に対する近似率

LP  A1  A2  A3  CUT
2n  ratio half int. ratio  ratio  ratio  ratio
16 1.00000 0.00000 1.00000 1.00000 1.00000 1.00158
18 0.99998 0.01307 1.00075 1.00246 1.00121 1.00295
20 0.99992 0.02158 1.00092 1.00282 1.00184 1.00236
22 1.00000 0.01688 1.00001 1.00329 1.00072 1.00385
24 1.00000 0.00471 1.00001 1.00000 1.00015 1.00423
26 1.00000 0.00000 1.00000 1.00000 1.00000 1.00357
30 0.99969 0.03172 1.00359 1.00875 1.00496 1.00635
40 0.99994 0.00654 1.00017 1.00187 1.00047 1.01007

表 3: 総移動回数最小化問題に対する近似率

LP  A1  A2  A3  CUT
2n  ratio half int.  ratio  ratio  ratio  ratio
16 0.88831 1.00000  1.19226  1.15681  1.07847  1.00138
18 0.88831 1.00000  1.21044  1.15005  1.06241  1.00205
20  (1) 1.00000 (1.36700) (1.28850) (1.22000) (1.13200)
22  (1) 1.00000 (1.37355) (1.30248) (1.21240) (1.13388)
24  (1) 1.00000 (1.38330) (1.29931) (1.21667) (1.13924)
26  (1) 1.00000 (1.38817) (1.31124) (1.21746) (1.14941)
30  (1) 1.00000 (1.40467) (1.30378) (1.22533) (1.15067)
40  (1) 1.00000 (1.42725) (1.30700) (1.22800) (1.15688)

表 4: 会場割当問題に対する CPU time [s]

A1  A2  A3  CUT  IP
2n  ave.  s. d. ave.  s. d. ave.  s. d.  ave.  s. d.  ave.  s. d.
16 0.042 0.0042 0.103 0.0082 0.115 0.0085  24.829 0.6830 0.779 0.1370
18 0.055 0.0097 0.136 0.0165 0.162 0.0079  39.254 0.6962 1.379 0.0348
20 0.112 0.0063 0.315 0.0127 0.409 0.0110  65.079 1.7357 2.194 0.0448
22 0.274 0.0070 0.760 0.0156 0.945 0.0172  99.201 1.9557 3.433 0.0150
24 0.628 0.0063 1.747 0.0241 2.109 0.0050 145.823 3.7068 5.599 0.2223
26 0.897 0.0106 2.517 0.0231 3.192 0.0469 224.273 10.2988 7.308 0.2204
30 1.205 0.0097 3.453 0.1302 3.854 0.2070 411.561 7.7994 13.855 0.3937
40 2.193 0.0206 6.240 0.0501 7.766 0.1773 1955.173 26.2481 52.991 0.3504

表 5: 総移動回数最小化問題に対する CPU time [s]

A1  A2  A3  CUT  IP
2n  ave.  s. d.  ave.  s. d.  ave.  s. d.  ave.  s. d.  ave.  s. d.
16 0.042 0.0042 0.162 0.0042 0.179 0.0088  21.701 0.4570  65.900  66.1060
18 0.053 0.0048 0.212 0.0042 0.245 0.0053  32.844 0.7563 2737.900 4999.0000
20 0.119 0.0032 0.520 0.0047 0.613 0.0067  53.550 1.1190  –  –
22 0.278 0.0042 1.267 0.0048 1.438 0.0169  82.185 1.4721  –  –
24 0.648 0.0042 2.997 0.0048 3.347 0.0330 120.208 3.1711  –  –
26 0.926 0.0053 4.330 0.0047 5.004 0.0375 189.170 6.6839  –  –
30 1.242 0.0042 5.840 0.0082 5.964 0.0201 399.349 7.1816  –  –
40 2.227 0.0082 10.739 0.0120 12.471 0.0574 2157.351 69.2466  –  –

2n:チーム数 ; ratio: IP の最適値と, 得られた最良解の目的関数値の比の平均;

括弧内の数値は IP の最適値の代わりに, その線形緩和問題の最適値を用いたもの; half int.: 緩和問題の最適解で値が 1/2 となった変数の割合; A1, A2, A3: 解法 A1, A2, A3; CUT: Goemans, Williamson [11] に基づく解法; IP : Trick [35] による整数計画に基づく定式化を, 整数計画法用ソフトウェアで解いたもの; avg.: 平均; s. d.: 標準偏差.

表 6: ホーム (H) ・アウェイ (A) ゲームのパターン

J リーグ 2001 年シリーズ前半戦ブレーク数
磐田  : HAHAH\underline{H}AHAHAHAHA  1
市原  : AH\underline{H}AHAH\underline{H}AHAHAH\underline{H}  3
名古屋 : HAHAHAH\underline{H}AHAHAHA  1
浦和 : AH\underline{H}AHAH\underline{H}AHAHA\underline{A}\underline{A} 4
Ｃ大阪 : HAHA\underline{A}HAHAHAHAHA  1
札幌  : AHAHAHA\underline{A}HAHAHAH  1
福岡  : HA\underline{A}HAHA\underline{A}HAHAH\underline{H}A  3
Ｇ大阪 : AHAH\underline{H}AHAHAHAHAH  1
横浜  : HA\underline{A}HAHAHA\underline{A}HAH\underline{H}A  3
神戸  : AH\underline{H}AHAHAHAHAHAH  1
Ｆ東京 : HA\underline{A}HAHAHAHA\underline{A}H\underline{H}A  3
東京Ｖ : AH\underline{H}AHAHAHAH\underline{H}A\underline{A}H  3
柏  : HA\underline{A}HAHA\underline{A}HAHAHAH  2
清水  : AHAHA\underline{A}HAHAHAHAH  1
鹿島  : HA\underline{A}HAHAHAHAHAHA  1
広島  : AH\underline{H}AHAHAH\underline{H}AHA\underline{A}H  3
セリエ A 2000/2001 年シリーズ前半戦ブレーク数
Atalanta : HA\underline{A}HAHAHAHAH\underline{H}AHAH  2
Bari  : HAHAH\underline{H}AHAHAHA\underline{A}HAH  2
Bologna  : AHAHAH\underline{H}AHAHAHAHAH  1
Brescia  : AH\underline{H}AHAHA\underline{A}HAHAHAHA  2
Fiorentina : AHAH\underline{H}AHA\underline{A}HAHAHAHA  2
Inter : AHAHAH\underline{H}AHAHA\underline{A}HAHA 2
Juventus : AHAHAHAHAHA\underline{A}H\underline{H}AHA  2
Lazio  : AHAH\underline{H}AHAHAHAHAHAH  1
Lecce  : AHAHA\underline{A}HAHAHAH\underline{H}AHA  2
Milan  : HAHAHA\underline{A}HAHAH\underline{H}AHAH  2
Napoli  : HAHAHAHAHAH\underline{H}A\underline{A}HAH  2
Parma  : HA\underline{A}HAHAH\underline{H}AHAHAHAH  2
Perugia  : HAHA\underline{A}HAH\underline{H}AHAHAHAH  2
Reggina  : HAHAHA\underline{A}HAHAHAHAHA  1
Roma  : HAHA\underline{A}HAHAHAHAHAHA  1
Udinese  : HAHAHAHAHAH\underline{H}AHAHA  1
Verona  : AH\underline{H}AHAHAHAHA\underline{A}HAHA  2
Vicenza  : AH\underline{H}AHAHAHAHA\underline{A}HAHA  2