HAT Feasibility Problem

スポーツスケジューリングの近年の展開
東京大学大学院情報理工学系研究科
松井知己
東京農工大学工学部情報コミュニケーション学科
宮代隆平
スポーツスケジューリングの近年の展開
東京大学大学院情報理工学系研究科
松井知己
発表の概要






はじめに
スケジュール
スケジュール＋試合場所
スケジュール→HAT
HAT→スケジュール
応用と実用
3
はじめに
はじまりは，６年前．．．．．
はじめに
G. L. Nemhauser and M. A. Trick,
“Scheduling a Major College Basketball Conference,”
Operations Research, 46(1998), 1‐8.
米の大学バスケ対抗リーグ戦（9チーム）の
スケジューリングを行った論文
（実際の現場，アルゴリズムの枠組み）
5
スポーツ・スケジューリング
 スポーツ・スケジューリング（対戦日程計画）
• Timetabling の一分野

スポーツ競技などの最適な対戦日程を決める

スケジュール作成アルゴリズムの構築
• 初期の研究： 1970 年代後半
ここ数年で研究が活発化
Timetabling の中でも大きな分野に
6
Bibliography on Practice and Theory of Automated
Timetabling
 http://liinwww.ira.uka.de/bibliography/Misc/timetabling.html
～1995まで論文数の推移
7
スポーツ・スケジューリングの実例
 スケジューリングの目的
• 移動距離最小化，観客数最大化，
公平性最大化，… → 収益最大化
 スケジュールへの要求
• 試合開催場所，固定された試合，
TV中継，各チームの強さ，予備日，…
現実問題から発生した研究分野
8
現在の手法
 研究者がスケジューリングに用いている手法
• 制約論理法
• メタ・ヒューリスティクス

SA, GA, ローカルサーチ，タブーサーチ，…
• 数理計画法

整数計画，分枝限定法，組合せ多面体論，…
 スケジューリング問題の理論的研究
• 抽象化された問題，先行研究ともに少ない
• グラフ理論，デザイン理論，実験計画法，…
近年の結果について概観する
9
Section 1 スケジュール
スケジュール
①
巨人：中
阪神：ヤ
広島：横
中日：巨
横浜：広
ﾔｸﾙﾄ：阪
(チーム)
②
阪
巨
中
広
ヤ
横
③
横
中
ヤ
阪
巨
広
④
広
横
巨
ヤ
阪
中
⑤ （スロット）
ヤ
広
阪
横
中リーグ戦のスケジュール
巨
・チーム数：2n
・スロット（試合日）：2n－1
チーム数が奇数の時はダミーのチームを加える
11
総当りリーグ戦とグラフ




各チームを頂点とする完全グラフ．
各枝は試合に対応する．
各試合日には，全てのチームが１試合を戦う．
各試合日の試合は，グラフ上の完全マッチング．
F
F
A
E
A
E
B
D
B
D
C
C
12
スケジュールの存在性 [Kirkman 1847 or earlier]
 以下のような円盤を回して，試合を決める．
A
A
A
A
A
E
E
E
B
B
B
E
B
B
F
E
F
F
F
F
D
C
D
C
D
C
D
C
D
C
１２３４５
A：F C E B D
B：E F D A C
C：D A F E B
D：C E B F A
E：B D A C F
F：A B C D E
12チームの場合
このまま回転を続ける‥‥.
13
実際のスケジュールは？
同一性判定
 与えられた２つのスケジュールがチーム名の付け
替えで、一致するか？ O(n3)
（2n :チーム数）
O(n2) × n
１２３４５
：中阪
巨 A：F
C横
E 広
B Dヤ
広 B：E F D A C
阪 C：D A F E B
ヤ D：C E B F A
横 E：B D A C F
中 F：A B C D E
１２３４５
巨人：中阪横広ヤ
阪神：ヤ巨中横広
広島：横中ヤ巨阪
中日：巨広阪ヤ横
横浜：広ヤ巨阪中
ﾔｸﾙﾄ：阪横広中巨
巨広阪ヤ横
 スロットの順も入れ替えてよいときは？ NP完全？
14
部分スケジュール完成問題
１２３４５６７８９
Ａ：ＪＦＧＣＨＢ
Ｂ：ＩＧＤＦＥＡ
10チームのリーグ戦
Ｃ：ＨＤＥＡＦＧ
6日目まで作成済み
Ｄ：ＧＣＢＪＩＥ
7日目以降の
Ｅ：ＦＪＣＨＢＤ
対戦を組みたい
Ｆ：ＥＡＩＢＣＨ
Ｇ：ＤＢＡＩＪＣ
Ｈ：ＣＩＪＥＡＦ
Ｉ：ＢＨＦＧＤＪ
Ｊ：ＡＥＨＤＧＩ
15
スケジュール完成問題のNP完全性
NP完全な問題
1. ３つのスロット以外がすべて埋められているとき、残
りの３スロットを上手に埋めて、スケジュールを完成
できるか？ [Easton, 2003]
2. 禁止集合P：(i,j,k) ∈P ⇔チームiとjの戦いはスロットk
で行ってはいけない。Pで与えられる禁止制約を守
るスケジュールが存在するか？ [Schaerf]
スケジュールに対応する多面体の記述は困難（？）
変数 x (i,j,k)∈｛0,1｝（チームiとjの戦いはスロットkで行うなら1．)
としたときのスケジュールのcharacteristic vector の凸包は、
separation problem の多項式時間解法無し（？）
16
Premature Sets [Rosa and Wallis]
 いくつかのスロットを埋めた時、それを満たしてスケ
ジュールを完成できるか？
premature set：スケジュールを完成できない,部分割当
定理[Rosa and Wallis]
nスロットの premature set は存在する。
２n＞６ならば、3スロット以下のpremature set は無い。
3スロットまでは、どう決めても大丈夫
Open Problem: 最小 premature set のサイズは？
17
Carry Over Effects （COE)
阪神は横浜にcoeを与える
…
阪神はヤクルトにcoe を与える
ヤクルトは横浜にcoeを与える
横浜は巨人にcoeを与える
…
１２３４５
巨人：中阪横広ヤ
阪神：ヤ巨中横広
広島：横中ヤ巨阪
中日：巨広阪ヤ横
横浜：広ヤ巨阪中
ﾔｸﾙﾄ：阪横広中巨
COEは、できるだけ均等に分散している方が良い。
18
COEを均等に分布させる
 完全に均等になるか？
 2n = 2k ならば、完全に均等にできる [Russell (1980)]
8チームの場合
1:4567823
2:5483617
3:8652471
4:1276358
5:2138746
6:7314285
7:6841532
8:3725164
19
COE値最小化の現状
2n
6
8
10
12
14
16
18
20
Value （チーム順序対毎のCOE数の2乗和）
60 (optimal Henz, Mueller, Thiel)
56 (optimal Russell)
122 (Trick)
188 (HMT and van Brandenburg)
260 (Russell)
240 (optimal, Russell)
428 (Russell)
520 (Russell)
20
Section 2 スケジュール + 試合場
場所付き総当りリーグ戦
各チームに本拠地があり，どちらかの本拠地で試合
• 本拠地での試合：ホームゲーム
• 遠征先での試合：アウェイゲーム
１
１：３
２：４
３：１
４：２
２
２
１
４
３
３
４ ← 1対4 （1の本拠地）
３
２
対応
１ ← 1対4 （1の本拠地）
スケジュール（4チーム）
22
試合場所の割当（HAT)
①
巨人：中
阪神：ヤ
広島：横
中日：巨
横浜：広
ﾔｸﾙﾄ：阪

②
阪
巨
中
広
ヤ
横
③
横
中
ヤ
阪
巨
広
④
広
横
巨
ヤ
阪
中
⑤
ヤ
広
阪
横
中
巨
① ② ③ ④ ⑤
巨：ＡＡＨＡＨ
阪：ＡＨＡＡＨ
→ 広：ＨＨＡＨＡ
中：ＨＡＨＡＨ
横：ＡＨＡＨＡ
ヤ：ＨＡＨＨＡ
Home-Away Table (HAT)
各試合をどちらの本拠地で行う？
Ｈ：ホーム
Ａ：アウェイ
23
ブレーク
 ＨＡ割当の質の指標：「ブレーク」
 チーム t がスロット s にブレークを持つ ⇔
… s－1 s …
… s－1 s …
t ： … ＡＡ … もしくは t ： … ＨＨ …
t：ＡＡＡＡＨＨＡ → （チーム t のブレーク数）＝ 4
 HHブレークとAAブレークは，（スロット毎に）同じ数．
AA
AA
AH
HA
HH
HH
24
ブレーク数の下界[de Werra]
ブレーク数の意味で最も良いHATは？
(ブレーク数が少ない方が良い.)
ブレーク最小 HAT [de Werra’80]
補題：ブレーク数の最小値 ≧ チーム数－2
証明：ブレークの無いHA-パターンは２つ
AHAHAHAHAHAHA
HAHAHAHAHAHAH
（HAHAHAHAHAHAH）
許容HATの行は互い異なるHAパターンを持つ．
2チームはブレークを持たない.
他のチームは１つ以上のブレークを持つ.
25
ブレーク最小HATのスケジュール[de Werra]
 ホームゲーム･アウェイゲームを決める．
A
A
B E
E
F
D
B E
D
A
B
E
F
F
C
A
B E F
A
C
１２３４５
A：F C E B D
B：E F D A C
C：D A F E B
D：C E B F A
E：B D A C F
F：A B C D E
D
C
D
アウェイ
ゲームチーム
C
D
F
B
C
ホーム
ゲームチーム
26
実際のスケジュールは？
ブレーク均等HATのスケジュール
 ブレーク数 2n－2 → 若干の不公平
• 全てのチームが 1個ブレークを持つＨＡ割当
①②③④⑤
１：ＡＨＡＨＡ
２：ＨＡＨＡＨ
３：ＡＨＨＡＨ
４：ＨＡＡＨＡ
５：ＡＨＡＨＨ
６：ＨＡＨＡＡ
ブレーク数 2n－2
ブレーク最小HAT
う）
①②③④⑤
１：ＨＨＡＨＡ
２：ＡＡＨＡＨ
３：ＡＨＡＡＨ
４：ＨＡＨＨＡ
５：ＡＨＡＨＨ
６：ＨＡＨＡＡ
ブレークが各チーム１個
ブレーク均等HAT
（ブレーク２n 個とは違
27
補完パターン[de Werra]
ブレーク最小HATの各行（HA-パターン）は下記のよう
にブレークが1つ(以下)のもの．
HAHAHAHAHHAHAHA ：HA-パターン
AHAHAHAHAAHAHAH ：補完パターン
補題：ブレーク最小HATが，あるHA-パターンを含む
ならば，その補完パターンも含む．
証明：（背理法）
s
あるパターン： ‥‥‥‥AHAAHA‥‥‥‥‥
‥‥‥‥HAHAHA‥‥AA ‥
‥‥‥‥HAHAHA ‥ HH‥‥
‥‥AA‥AHAHAH‥‥‥‥‥
sスロットとs+1スロットのHとAの数が異なる．矛盾.
28
ブレーク最小とブレーク均等スケジュール
 （ブレーク最小HAT＋スケジュール）は、ブレーク位
置でユニークに表現できる
 最終スロットと開始スロットをつなげる．
１０１０１
するとブレークがあるのはn箇所
１２３４５
A：F C E B D
F：A B C D E
B：E F D A C
 開始スロットが
C：D A F E B
ブレークが有る所：ブレーク最小 D：C E B F A
ブレークが無い所：ブレーク均等 E：B D A C F
各チームは（開始スロット含め）
ブレークが丁度1個で，
補完パターン対に分かれている
n個のブレーク最小HAT
n-1個のブレーク均等HAT
29
ブレーク最小化＝ブレーク最大化
[Miyashiro&M]
 ブレーク数最小化／最大化
• 従来は別々に議論
• でも，実は同じ問題
 与えられた入力に対して，
「ブレーク数最大化の最適解」
⇔ 「ブレーク数最小化の最適解」を行う変換
30
最小化／最大化の変換[Miyashiro&M]
 ＨＡ割当Τ
• 偶数スロットのHAを逆転
①②③④⑤
①②③④⑤
１：ＡＨＡＨＡ
１：ＡＡＡＡＡ
２：ＨＡＨＡＨ
２：ＨＨＨＨＨ
３：ＡＨＨＡＨ
３：ＡＡＨＨＨ
４：ＨＡＡＨＡ変換４：ＨＨＡＡＡ
５：ＡＨＡＨＨ ⇔ ５：ＡＡＡＡＨ
６：ＨＡＨＡＡ
６：ＨＨＨＨＡ
ＨＡ割当Τ
ＨＡ割当Τ’
（元のブレーク数）＋（変換後のブレーク数）＝2n(2n－2)
31
ブレーク最大化＋（３H，３A 禁止） [Russell & Leung]
 ３連続H, ３連続Aを持たないHATが存在するスケ
ジュールで，ブレーク数最大のものは？
定理 [Russell & Leung]
３連続H, ３連続Aを持たず、2n(n-1)-(2n-4) 以上のブ
レークが存在するHATを持つスケジュールが存在
する．
open problem: 上記の下界は，下限なのか？
32
Section 3 スケジュール → HAT
スケジュールの作成方法 [Regin]等
①②③
①②③
①②③
１：２４３
１：ＡＨＡ１：ＨＨＨ
２：１３４ → ２：ＨＨＡ２：ＡＡＡ
３：４２１
３：ＡＡＨ３：ＨＨＡ
４：３１２
４：ＨＡＨ，４：ＡＡＨ，…
入力：スケジュール
出力：対応するＨＡ割当
 制約条件：対戦ペアの片方はＨ，片方がＡ
（対戦制約）
→ 目的関数： “ブレーク数”
34
ＨＡ割当のブレーク数
ＨＡ割当に含まれるブレーク数
①②③
１：ＡＨＡ
２：ＨＨＡ
３：ＡＡＨ
４：ＨＡＨ 2個
①②③
１：ＨＨＨ
２：ＡＡＡ
３：ＨＨＡ
４：ＡＡＨ 6個
ブレーク数が小 → ＡとＨなるべく交互
ブレーク数が大 → Ａの連続，Ｈの連続
35
ブレーク数最適化問題
 ブレーク数最小化／最大化問題
• 入力：スケジュール（チーム数 2n）
• 出力：対戦制約を満たすＨＡ割当のうち，
ブレーク数が最小／最大のもの．
→ 最小化，最大化の意味，先行研究
36
ブレーク数最小化の目的
 ブレーク数最小化の目的
• できるだけＡとＨを交互に（公平性）
１２３４５
１：ＡＡＡＡＡ
２：ＡＨＡＨＡ
３：ＨＨＡＡＨ
４：ＨＡＨＡＡ
５：ＡＡＨＨＨ
６：ＨＨＨＨＨ (14)
１２３４５
１：ＡＨＨＡＡ
２：ＨＨＨＡＨ
３：ＡＨＡＨＡ
４：ＨＡＡＨＨ
５：ＡＡＨＡＨ
６：ＨＡＡＨＡ (8)
37
最小化問題の先行研究
 ブレーク数最小化問題
• NP-困難??
• 先行研究（分枝限定ベース）

Regin (1998), 制約論理，～チーム数20

Trick (2000), 整数計画，～チーム数22

Elf, Jünger, Rinadi (2003), MAX CUT ＋ ABACUS,
～チーム数26
• Elf et al. による予想（後述）
38
最小化の計算時間
チーム数
16
18
20
22
24
26
Regin (CP)
5
80
5603
CPU
200MHz
環境 Solver (ILOG)
Trick (IP)
34
43
1092
7802
266MHz
CPLEX (ILOG)
Elf 他 (MAX CUT)
1
6
9
37
73
339
（単位：秒）
300MHz
ABACUS
39
ブレーク数最大化の目的 [Rusell&Leung]等
 ブレーク数最大化の目的：移動距離最小化
• ＨＡＨＡＨ→ＨＨＨＨＨ
•ＨＡＨＡＨ→ＡＡＡＡＡ
→ 経験的に，移動距離最小化問題の
良い解を与える
（大リーグの3軍など）
40
最小(¼) –最大(¾)の存在[Miyashiro&M]
（元のブレーク数）＋（変換後のブレーク数）=4n(n－1)
定理 [Miyashiro&M] 任意のスケジュールは，それに対
応するHATで，ブレーク数が n(n－1) 以下のものを
持つ．（3n(n－1) 以上のものも持つ．）
ブレーク無し
スロットを, 2スロット以降を２つづ区切る．
対の後ろのスロットは，ブレークを無くす．
各対毎に，HAを(1/2)の確率で反転．
ブレーク総数の期待値は n(n-1)
2n
第 i スロット
第 i +1スロット
2n-1
各スロットのブレーク数の期待値 n
41
最大化問題の先行研究
 ブレーク数最大化問題
• NP-困難??
• 移動距離最小化問題の暫定解を生成

Rusell, Leung (1980)

Easton, Trick, Nemhauser (2001, 2003)
 ブレーク数最小化，最大化は
これまで別々な議論
42
先行研究と最大化
 Trick (2000) の IP による定式化
• Naïve な定式化： min, max ともに遅い
→ 妥当不等式を導入
花不等式（小さな奇集合のみ）
 Elf et al. (2003)：ブレーク最小化 → MAX CUT
• ブレーク最大化 → MIN CUT
43
最小HAT存在判定を２SATで解く
[Miyashiro&Matsui 2004]
OR Letters
先行研究の予想
 ブレーク数最小化問題の計算複雑度
• NP-困難 ??
• Elf et al. (2003)；最小化問題
最小ブレーク数が小さい入力 → 計算時間小
• 特に「最小ブレーク数＝2n－2 の例」は
短時間で最適解が求まる（チーム数：2n）
→ 何らかの特殊構造，多項式時間性??
彼らの予想： MAX CUT が多項式時間で解ける
グラフのクラスと関連？
45
ブレーク数の判定問題
問題 (P)
入力：チーム数 2n のスケジュール
出力：ブレーク数 2n－2 のＨＡ割当；
存在しないなら不能．

ブレーク数最小化問題の
判定問題version; 目的関数値 2n－2
 O(n3) アルゴリズムを開発
46
問題の変換
問題 (P)
入力：チーム数 2n のスケジュール
出力：ブレーク数 2n－2 のＨＡ割当；
存在しないなら不能．
（ブレーク数 2n－2）
←（変換）→（ブレーク数 2n(2n－2) － (2n－2)）
問題(P’)
出力：ブレーク数 2n(2n－2) － (2n－2) のＨＡ割当；
存在しないなら不能．
47
ＨＡ割当の変換
ブレーク数 2n－2
①②③④⑤
１：ＡＨＡＨＡ
２：ＨＡＨＡＨ
３：ＨＨＡＨＡ
４：ＡＡＨＡＨ
５：ＡＨＡＡＨ
６：ＨＡＨＨＡ
ブレーク数 2n(2n－2)－(2n－2)
①②③④⑤
１：ＡＡＡＡＡ
２：ＨＨＨＨＨ
３：ＡＡＨＨＨ
４：ＨＨＡＡＡ
５：ＡＡＡＨＨ
６：ＨＨＨＡＡ
 ブレーク 0個のチーム → 全てＡ or 全てＨ
 ブレーク 1個のチーム → 1回だけＡ→Ｈ or Ｈ→Ａ
48
変換後の問題
①②③④⑤
１：ＡＨＨＨＨ
問題 (P’)：左のような
２：ＡＡＡＨＨ
ＨＡ割当が存在？
３：ＨＡＡＡＡ
注意：対戦制約
４：ＨＨＨＨＨ ← 全てＨ
５：ＡＡＡＡＡ ← 全てＡ
６：ＨＨＨＡＡ ← 1回だけ替わる
子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i＜j )
• チーム i が全てＡ，チーム j が全てＨと固定
49
子問題のＨＡ割当
子問題 (Pi,j’) ( i, j = 1, 2, …, 2n, i＜j )
•
チーム i が全てＡ，チーム j が全てＨと固定
① ② ③ ④ ⑤
１：４
２：６
３：５
４：１
５：３
６：２

２５
１４
４６
３２
６１
５３
入力
３
５
１
６
２
４
６
３
２
５
４
１
① ② ③ ④ ⑤
１：Ａ
Ｈ
２：
Ａ
Ｈ
３：ＡＡＡＡＡ
４：ＨＨＨＨＨ
５：Ｈ
Ａ
６：
ＨＡ
子問題(P34’)
残りのチーム：Ａ…ＡＨ…ＨもしくはＨ…ＨＡ…Ａ
となる，対戦制約を満たすＨＡ割当が存在するか？
50
制約条件の伝播
① ② ③ ④ ⑤
① ②
１：Ａ
Ｈ
１：Ａ
２：
Ａ
Ｈ
２：ＡＡ
３：ＡＡＡＡＡ → ３：ＡＡ
４：ＨＨＨＨＨ
４：ＨＨ
５：Ｈ
Ａ
５：Ｈ
６：
ＨＡ
６：ＨＨ

③ ④
Ｈ
Ａ
ＡＡ
ＨＨ
⑤
Ｈ
Ｈ
Ａ
Ｈ
Ａ
ＨＡＡ
制約条件：Ａ→Ｈ or Ｈ→Ａが 1回，入力に対応
→ Ｈを FALSE, Ａを TRUE とすれば，
2SAT として定式化可能．
51
計算複雑度の算定
 制約式
• Ａ→Ｈ，Ｈ→Ａが1回だけ起きる
• 対戦制約を満たす
→ 2SAT で定式化可能！
 2SAT: 変数，2-クローズの個数 O(n2)
→ 子問題 1個あたり O(n2), 問題(P) は O(n4)
 アルゴリズムの工夫 → O(n3)
52
ブレーク数 2n－2 に対する結果
問題 (P)
入力：チーム数 2n のスケジュール
出力：ブレーク数 2n－2 のＨＡ割当；
存在しないなら不能．
 O(n3) アルゴリズム
• ブレーク数 2n－2 の解 → 最小化問題の最適解
• Elf たちの予想に対する一つの答え
53
ブレーク均等HATのケース
問題 (Q)
入力：チーム数 2n のスケジュール
出力：全てのチームがブレークを1個持つＨＡ割当；
存在しないなら不能．
 O(n3) アルゴリズムを開発
54
ブレーク数最小化問題をSDP緩和で解く
[Miyashiro&Matsui 2004]
Computers and OR (SS 特集）
ブレーク数がチーム数以上
 与えられたスケジュールが，
ブレーク数 2n 以下のＨＡ割当を持たない場合は？
→ 先行研究（分枝限定ベース）では，
計算時間がかかる
• 最小ブレーク数が大きい問題例
• チーム数の大きな問題
56
SDP 緩和を用いたアルゴリズム
 半正定値計画緩和を用いた
多項式時間確率的アルゴリズム
• MAX RES CUT として定式化
• Goemans, Williamson (1995) の
0.878 確率的近似アルゴリズムを適用
• 極めて高速な，質の良い解の生成を確認
57
MAX RES CUT
MAX RES CUT
入力：無向グラフ G=(V, E), 各枝に対する非負重み
＋頂点ペア {vi1, vj1}, …, {vik, vjk}
出力：頂点ペア{vi1, vj1}, …, {vik, vjk}を分け，
重み最大のカット集合
 NP-困難
 Goemans, Williamson (1995) による
0.878 確率的近似アルゴリズム
58
ブレーク数最小化問題と MAX RES CUT
①②③
１：２４３
①
１ ●
②
●
③
●
２：１３４
２ ●
●
●
３：４２１
３ ●
●
●
４：３１２
４ ●
●
●
A
頂点集合を「Ａの集合」と「Ｈの集合」に分割
カット＝ブレーク無
H
59
制約のSDPへの導入
 MAX RES CUT
• 制約：「頂点 v, v’がカットで分けられる」
• xv xv’ = －1, uv・ uv’ = －1, yvv’= －1
uv
uv’
60
MAX RES CUT のグラフ
チーム数頂点数
16
18
20
22
24
26
30
40
枝数
240 288
306 224
380 360
462 440
552 528
650 624
870 840
1560 1520
近似比
計算時間[秒]
1.000
2.1
1.000
3.4
0.994
4.9
0.995
8.0
0.989
12
0.985< 18
?
38
?
179
61
計算実験の結果
チーム数
16
18
20
22
24
26
30
40
最適値（IP）
192
248
312
382
458
540 or 542
―
―
SDP緩和
192
248
310
380
452
534
720
1306
差
0
0
2
2
4
6 or 8
?
?
近似比率
1.000
1.000
0.994
0.995
0.989
0.985<
?
?
（超平面分離1000回）
62
計算時間の比較
チーム数
16
18
20
22
24
26
30
40
Régin
1
18
1245
Trick
6.5
13
323
678
（2ヶ月<）
Elf et al.
0.3
2
3
12
24
111
本研究 [秒]
2.1
3.4
4.9
8.0
12
18
38
179
(CPU: 900 MHz, SDP Solver: SDPA 6.0, 超平面分離1000回)
63
アルゴリズムの利点
 非常に質の良い解を出力（最適解の 98.5% 以上）
• 理論的な近似比保証（87.8% 以上）
 従来より大規模な問題に適用可能
 計算時間が非常に速い
• 厳密解法の暫定解としても利用可能
• パラメータチューニングなどが不要
64
Section 4 HAT→スケジュール
スケジュールの作成方法
１２３
１２３
１：２４３
１：２４３
２：１３４ → ２：１３４
３：４２１
３：４２１
４：３１２
４：３１２
① 対戦相手決定
② 場所を割当
線
１２３
１２３
１：ＡＨＡ
１：２４３ ① HATを決定
２：ＨＨＡ → ２：１３４ ② 対戦相手を割当
３：ＡＡＨ
３：４２１
４：ＨＡＨ
４：３１２
66
許容HAT
HAT作成 →（チーム割当）→ スケジュール作成
１２３
１：ＡＨＡ
２：ＨＨＡ →
３：ＡＡＨ
４：ＨＡＨ
１２３
１２３
１：２４３１：２３４
２：１３４２：１４３
３：４２１３：４１２
４：３１２，４：３２１
許容HAT：スケジュールを生成できるHAT
cf. 不能HAT
67
HAT 許容性判定問題
HAT 許容性判定問題
Input: HAT （チーム数 2n; 2n－1 スロット）;
Output: 与えられたHATが許容HATか？
• 長年の未解決問題 [de Werra 1980,
Nemhauser & Trick 1998]
• 理論的結果ほぼ無し（整数計画法）
• 計算複雑度は未知（NP-完全??）
目標：「許容HATの良い特徴付け」
68
許容HATである必要条件
１２３４５
１２３４５
１：ＡＡＨＡＨ１：ＡＡＨＡＨ
２：ＡＨＨＡＨ２：ＡＨＨＡＨ
３：ＡＨＡＡＨ３：ＡＨＡＡＨ
４：ＨＨＡＨＡ
０１１００
５：ＨＡＡＨＡ
６：ＨＡＨＨＡ
min{#Ａ, #Ｈ}
α({1,2,3}) = (0+1+1+0+0) － 3×2/2 = －1 ⇒ 不能
α(T) ＝ ∑s min{#Ａ(T, s), #Ｈ(T, s)} － |T| C 2
69
関数αの定義
許容HATの必要条件
∀T⊆U, ∑s min{#Ａ(T, s), #Ｈ(T, s)} ≧ |T| C 2
関数αの定義
α(T) ＝ ∑s min{#Ａ(T, s), #Ｈ(T, s)} － |T| C 2
許容 HAT であるための必要条件 Ⓐ
∀T⊆U, α(T)≧0
70
許容HATの必要条件
許容HAT の必要条件 Ⓐ： ∀T⊆U, α(T)≧0
• 22n 本の不等式による表現
HAT 許容性判定における新たな解析手法
→ 特殊なクラスの HAT を考え，
それらの許容性と条件 Ⓐ の関係を考察
（最小HAT と均等HAT, 十分条件？）
71
許容性判定と条件Ⓐ
 一般的に好ましい HAT
• ブレーク最小HAT (ブレーク数 2n－2),
• ブレーク均等HAT (ブレーク数 2n)
→ これらの HAT の許容性を簡単に判定したい
 条件Ⓐ 「∀T⊆U, α(T)≧0」がどのくらい有効か？
→ 計算機実験により評価
72
計算実験の結果
#teams
4
6
8
10
12
14
#総数
3
10
35
126
462
1716
# Ⓐ #許容 #teams
3
5
14
18
55
91
3
5
14
18
55
91
#Ⓐ
#許容
16
6435 255
18
24310 408
20
92378 1102
22 352716 1995
24 1352078 5313
26 5200300 9850
255
408
1102
1995
5313
9850
#総数
26チーム以下の最小HAT，均等HATならば，
「∀T ⊆U,α(T)≧0 ⇔ 許容HAT」
73
実験結果のまとめ
 提案した条件 Ⓐ は，非常に強い必要条件
• 26チーム以下の最小HAT，均等HATの場合
∀T⊆U, α(T)≧0 ⇔ 許容HAT

28チーム以上は未実験
（30チームまでは確認 [池辺 2003]）
• 未解決予想：任意のチーム数で必要十分条件
74
定理の概要
 ∀T⊆U ={1,2,…,2n} に対してα(T) を考えると...
• 22n 本の不等式をチェック？
証明した定理
任意のチーム数の最小HAT，均等HATに関して，
「∀T⊆U, α(T) ≧ 0 （条件 Ⓐ ）」を満たすか否かは
O(n4)でチェック可能
75
条件Ⓐに関する定理
定理：（チーム番号を前処理でソート後）
任意の均等HAT （最小HAT）について，
∀T⊆U, α(T) ≧ 0
不等式 O(22n) 本
⇔
全ての連続な T⊆U に対して α(T) ≧ 0
不等式 O(n2) 本
 連続な T : {1, 2, 3}, {5, 6}, {2, 3, 4, 5}, …
 非連続な T : {1, 2, 4}, {5, 7}, {2, 5, 6, 7}, …
76
成果の応用
 実用上は，均等HATの中でも
さらに “良い” 均等HAT を求めるケース有
• 許容である
• スロット 2, 2n－1 のブレークをできるだけ避ける．
[Nemhauser&Trick 1998]
77
望ましいHATの総数
 スロット 2, 2n－1にブレークがない
許容な均等HAT は？ [宮代，松井 2002]
→ チーム数14以下では存在しない（許容HAT)
チーム数16 ： 1個
（２５５個）
チーム数18 ：存在しない
（４０８個）
チーム数20 ： 4個
（１１０２個）
…
条件Ⓐ の許容均等HAT列挙への応用
78
MIM予想と柏原の反例 [Miyashiro,Iwasaki,M]
予想[Miyashiro,Iwasaki,M]
最小HATと均等HATにおいて、
∀T⊆U, α(T) ≧ 0は、
許容となる必要十分条件。
appearing in recent handbooks
[Ikebe]により、30チームまで
反例が無いことが確認された。
一般のHATでは十分でない。
柏原による反例
01:HHHHAAAAHAAAH
02:HHHHAAAAHHAAA
03:HHHHAAAAAHHAA
04:HHHHAAAAAAHHA
05:HHHHAAAAAAAHH
06:HHHHHHHHAAAAH
07:AAAAHHHHHAAAH
08:AAAAHHHHHHAAA
09:AAAAHHHHAHHAA
10:AAAAHHHHAAHHA
11:AAAAHHHHAAAHH
12:HHAAHAAAHHHHH
13:AAHAAHAAHHHHA
14:AAAHAAHHHHHHH
79
Section 5 応用と実用
Traveling Tournament Problem
http://mat.gsia.cmu.edu/TOURN/ (see Trick’s HP)
2重総当り戦 : n で 2n-2 スロット
目的は、総移動距離の最小化（各チームは、自分の
ホームから出発し、自分のホームに帰ってくる）
どのチームも、3H と 3A は禁止
No repeaters (A 対 Bの直後の B 対 A は禁止)
距離行列は、対称
81
８チームの問題例（NL8)
 Feasible Solution:
•
•
•
•
•
41505 (Easton June 4, 1999),
41113 (Easton Jan 27, 2000),
40416 (Cardemil, July 2 2002),
39947 (Zhang, August 19 2002),
39721 (Easton, August 25 2002)
 Lower Bound:
• 38760 (Trick Dec 15, 2000),
• 38870 (Easton Jan 2, 2001),
• 39479 (Easton Feb 26, 2002)
82
１０チームの問題例（NL10)
 Feasible Solution:
•
•
•
•
•
•
68691 (Rottembourg and Laburthe June 2001),
66369 (Dorrepaal, June 21 2002),
66037 (Cardemil, July 2 2002),
64597 (Zhang August 6, 2002),
61608 (Zhang August 19, 2002),
59583 (Van Hentenryck January 14, 2003)
 Lower Bound:
• 56506 (Waalewijn July 2001),
• 57500 (Easton June 2002)
83
１２チームの問題例（NL12)
 Feasible Solution:
• 143655 (Rottembourg and Laburthe May 2001),
• 138850 (Larichi, Lapierre, and Laporte July 8 2002),
• 125803 (Cardemil, July 2 2002),
• 119990 (Dorrepaal July 16, 2002),
• 119012 (Zhang, August 19 2002),
• 118955 (Cardemil, November 1 2002),
• 114153 (Van Hentenryck January 14, 2003),
• 113090 (Van Hentenryck February 26, 2003),
• 112800 (Van Hentenryck June 26, 2003),
• 112684 (Langford February 16, 2004),
• 112549 (Langford February 27, 2004),
• 112298 (Langford March 12, 2004),
• 111248 (Van Hentenryck May 13, 2004).
 Lower Bound:
• 107483 (Waalewign August 2001)
84
14チームの問題例（NL14）
 Feasible Solution:
•
•
•
•
•
•
•
•
•
301113 (Rottembourg and Laburthe June 2001),
262010 (Larichi, Lapierre, Laport July 8 2002),
216108 (Cardemil, July 2 2002),
207075 (Zhang, August 28 2002),
205894 (Cardemil, November 20 2002),
195555 (Van Hentenryck January 14, 2003),
190368 (Van Hentenryck February 26, 2003),
190056 (Langford April 22, 2004),
189766 (Van Hentenryck May 13, 2004).
 Lower Bound:
• 182797 (Waalewign August 2001)
85
16チームの問題例（NL16)
 Feasible Solution:
•
•
•
•
•
•
•
•
•
•
312623 (Easton January 2002),
308413 (Cardemil, July 2 2002),
301256 (Zhang August 6 2002),
293175 (Zhang, August 28 2002),
284235 (Shen, October 16 2002),
281660 (Shen, January 6 2003)
277766 (Van Hentenryck January 14, 2003),
273802 (Van Hentenryck February 26 2003),
272,902 (Langford, January 16, 2004),
267,194 (Van Hentenryck, June 26, 2003).
 Lower Bound:
• 248852 (Easton January 2002)
86
実例
 実例では？
 ３Hと３Aの禁止
 各チームのブレークは２回程度
87
1993年のＪリーグ前半戦(ブレーク数）
1
H
H
A
A
A
H
H
H
A
A
2 3 4 5
K:
H A A H
V:
A A H A
M:
H A A H
E:
H H A H
J:
H A H A
S:
A H H A
F:
A H A H
G:
A H H A
N:
A H H A
R:
H A A H
2 2 6 0
2重総当り戦
6
H
A
A
H
A
A
H
A
H
H
8
7
A
H
H
A
H
H
A
H
A
A
0
8
H
A
A
H
A
A
H
H
H
A
2
9101112131415161718
A A A H A A H A H H
H H A A H H A H A H
H A H H A H A H A H
A A H H A A H A H A
H A H A H H A H A H
H H A A H H A H A A
A H A H A A H A H A
A H A A H H A A H A
A H H A H A H A H A
H A H H A A H H A H
0 4 2 6 0 8 0 2 0 2
7
5
2
5
2
6
2
6
3
6
43
１０チーム
88
望ましい
2001年のＪリーグ後半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
0
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
A
H
H
H
A
H
A
H
A
H
A
A
A
H
A
2
A
H
A
A
A
H
A
H
A
H
A
H
H
H
A
H
0
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
4
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
A
A
A
A
H
H
H
A
H
A
H
A
H
H
H
A
2
H
H
H
H
H
A
A
A
A
H
A
H
A
A
A
H
2
A A
A A
A A
A A
A A
H H
H H
H H
H H
A H
H A
A H
H H
H H
H A
A A
012
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
0
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
2
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
0
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
8
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
0
3
2
3
2
3
3
2
3
1
1
1
1
2
3
1
1
32
16チーム
89
読み方
2001年のＪリーグ前半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
0
A H
H H
A H
H H
A H
H A
A A
H A
A A
H H
A A
H H
A A
H A
A A
H H
010
A
A
A
A
A
H
H
H
H
A
H
A
H
H
H
A
0
H
H
H
H
A
A
A
H
A
H
A
H
A
A
A
H
2
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
2
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
6
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
A
H
H
H
A
A
0
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
0
H
H
H
A
H
A
H
A
H
A
H
A
A
A
H
A
6
A
H
A
A
A
H
A
H
A
H
A
H
H
H
A
H
2
1
3
1
4
1
1
3
1
3
1
3
3
2
1
1
3
32
16チーム
90
読み方
セリエＡ2000/2001シーズン（２重総当たり戦）
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
HAAHAHAHAHAHHAHAH
HAHAHHAHAHAHAAHAH
AHAHAHHAHAHAHAHAH
AHHAHAHAAHAHAHAHA
AHAHHAHAAHAHAHAHA
AHAHAHHAHAHAAHAHA
AHAHAHAHAHAAHHAHA
AHAHHAHAHAHAHAHAH
AHAHAAHAHAHAHHAHA
HAHAHAAHAHAHHAHAH
HAHAHAHAHAHHAAHAH
HAAHAHAHHAHAHAHAH
HAHAAHAHHAHAHAHAH
HAHAHAAHAHAHAHAHA
HAHAAHAHAHAHAHAHA
HAHAHAHAHAHHAHAHA
AHHAHAHAHAHAAHAHA
AHHAHAHAHAHAAHAHA
AHHAHAHAHAHAAHAHA
AHAHAAHAHAHAHHAHA
HAHAHAAHAHAHAHAHA
HAAHAHAHHAHAHAHAH
HAHAAHAHHAHAHAHAH
HAHAHAAHAHAHHAHAH
HAHAHAHAHAHHAAHAH
HAHAAHAHAHAHAHAHA
HAHAHHAHAHAHAAHAH
AHAHAHHAHAHAAHAHA
AHAHAHAHAHAAHHAHA
AHHAHAHAAHAHAHAHA
AHAHHAHAAHAHAHAHA
AHAHAHHAHAHAHAHAH
AHAHHAHAHAHAHAHAH
AHAHAHAHAHAAHAHAH
HAAHAHAHAHAHHAHAH
HAAHAHAHAHAHHAHAH
91
セリエＡ2000/2001シーズン（２重総当たり戦）
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA
AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA
AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH
AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH
AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH
AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH
AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA
AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH
HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA
HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA
HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA
HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA
HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH
HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH
HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
92
セリエＡ2000/2001シーズン（ホームゲーム）
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
H H H H H HH H H HH H H H H H H
H H HH H H H H H H H H H H HH H
H H HH H H H H HH H H H H H H H
HH H H H H H H H H H HH H H H H
H HH H H H H H H H H HH H H H H
H H HH H H H H H H H H H HH H H
H H H H H HH H H H H H H HH H H
H HH H H H H H HH H H H H H H H
H H H H H HH H H H HH H H H H H
H H H H H HH H H H H HH H H H H
H H H H H HH H H H H H H H HH H
H H H HH H H H H HH H H H H H H
H H H HH H H H H H HH H H H H H
H H H H H H H H H H HH H H H H H
H H H H H H H H H HH H H H H H H
H H H H H HH H H H H H H H H H H
HH H H H H H H H H H H H HH H H
HH H H H H H H H H H H H HH H H
030212020022200020202120200132000
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
2
2
33
93
セリエＡ2000/2001シーズン（アウェイゲーム）
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
AA A A A A A A A A A A A AA A A
A A A A A AA A A A AA A A A A A
A A A A A A A A A A AA A A A A A
A A A AA A A A A AA A A A A A A
A A A AA A A A A A AA A A A A A
A A A A A AA A A A A AA A A A A
A A A A A AA A A A A A A A AA A
A A A A A A A A A AA A A A A A A
A A AA A A A A A A A A A A AA A
A A AA A A A A A A A A A AA A A
A A A A A AA A A A A A A AA A A
AA A A A A A A A A A AA A A A A
A AA A A A A A A A A AA A A A A
A A AA A A A A AA A A A A A A A
A AA A A A A A AA A A A A A A A
A A A A A A A AA A A A A AA A A
A A A A A AA A A AA A A A A A A
A A A A A AA A A AA A A A A A A
020212020013200030302120200222000
2
2
1
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
34
94
セリエＡ2000/2001シーズン（ブレーク数）
Atalanta :
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina
:
Roma
:
Udinese
:
Verona
:
Vicenza :
HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA
AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA
AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH
AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH
AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH
AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH
AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA
AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH
HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA
HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA
HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA
HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA
HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH
HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH
HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
050424040035400050504240400354000
２重総当り戦
4
4
3
4
4
4
4
3
4
4
4
4
4
3
3
3
4
4
67
95
課題
 各チームのブレーク２回の（スケジュール＋HAT）
の特徴付け．
 ２重総当り戦での，ブレーク数最小化
 ３Hと３Aの禁止
 移動距離
 観客動員数予想
課題：チーム数が小さくても，巨大(O(n5)変数)な2次非凸整数計画
96
おわり
97
98
Bibliography on Practice and Theory of Automated
Timetabling
 http://liinwww.ira.uka.de/bibliography/Misc/timetabling.html
～1995まで論文数の推移
99

Download Report