試合スケジュールの作成【GLPK】 #整数計画法

はじめに

リーグ戦のスケジュールを効率的に作成できるGLPKで動くプログラムを作ってみました。

最適化の条件

7チームでリーグ戦のスケジュールを作成する
複数の日に分散させて、各チームともに1日に1回しか試合ができない
同時に1試合しかできない
チーム数が変わってもデータセクションの変更で対応可能

まずこのような簡単な条件で作ったものを以下に書いておきます。

game_schedule01.mod

# version 0.1
set Date;    # 日付を読み込む
param nTeam; # チーム数を読み込む
param nGame{Date}; # 各日の試合数を読み込む

set Team := 1..nTeam; # チーム番号
set GameIndex := {d in Date, g in 1..nGame[d]}; # 日付とその日の試合番号
set Match := {i in Team, j in Team : i<j}; # 対戦の組み合わせ

var assignGame{GameIndex, Match} binary; # 試合の割り当てをする変数

# 同じ時刻には試合は1つだけ
s.t. oneGame{(d,g) in GameIndex}: sum{(t1,t2) in Match}assignGame[d,g,t1,t2]==1; 
# 対戦は一回ずつ
s.t. onceMatch{(t1,t2) in Match}: sum{(d,g) in GameIndex}assignGame[d,g,t1,t2]==1;
# 各チームの試合は1日以下
s.t. restrictGameTime{d in Date, t in Team}: sum{(d,g) in GameIndex, (t1,t2) in Match: t1==t or t2==t}assignGame[d,g,t1,t2]<=1;

solve;
# 出力
printf{(d,g) in GameIndex, (t1,t2) in Match : assignGame[d,g,t1,t2]==1} "%d   %d   %d - %d\n", d, g, t1, t2;

data;
# チーム数
param nTeam := 7;
# 日付とその日の試合数
param : Date : nGame :=
1    3
2    3
3    3
4    3
5    3
6    3
7    3
;

チーム単位でスケジュールを設定

次に、
チームごとに試合スケジュールを設定できるようにしました。
fixGameScheduleに
(日付, 試合番号, チーム番号)
を書くと個別に試合スケジュールを設定できます。逆に
avoidGameScheduleに書くとそこには試合が設定されません。

おまけとして、試合の時間帯を分散させるために、同じ試合番号になる試合は各チーム2回以下になる制限を追加しています。
(2018.2.3 追記)
各チーム2回以下に制限していますが、チーム数や試合数が変わってくると2回以下では条件を満たさなくなることがありますので、必要があれば調整してください。
s.t. restrictGame{ 〜
の行です。

データセクションに
(1, 1, *) 1 2
のような記述がありますが、これは
(1, 1, 1)
(1, 1, 2)
をまとめた書き方です。*の場所に1と2が入ります。
括弧のは*を含む場合には必要ですが、*がない場合には
1 1 1
1 1 2
のような書き方もできます。カンマも省略可能です。

以下の例では、
1日目の第1試合にチーム1と2
1日目の第2試合にチーム3と4
1日目の第3試合にチーム5と6
に試合を入れ
1日目の第1,2,3試合にチーム7は試合がない(つまりこの日は試合なし)
同じく
2日目にチーム6は試合なし
3日目にチーム5は試合なし
4日目にチーム4は試合なし
5日目にチーム3は試合なし
6日目にチーム2は試合なし
7日目にチーム1は試合なし
の条件になっています。

game_schedule02.mod

# version 0.2
set Date;    # 日付を読み込む
param nTeam; # チーム数を読み込む
param nGame{Date}; # 各日の試合数を読み込む
set fixGameSchedule dimen 3; # 試合をする時間を読み込む
set avoidGameSchedule dimen 3; # 試合を避ける時間を読み込む

set Team := 1..nTeam; # チーム番号
set GameIndex := {d in Date, g in 1..nGame[d]}; # 日付とその日の試合番号
set GameNumber := setof{(d,g) in GameIndex}(g); # 試合番号だけを取り出す
set Match := {i in Team, j in Team : i<j}; # 対戦の組み合わせ

var assignGame{GameIndex, Match} binary; # 試合の割り当てをする変数

# 同じ時刻には試合は1つだけ
s.t. oneGame{(d,g) in GameIndex}: sum{(t1,t2) in Match}assignGame[d,g,t1,t2]==1; 
# 対戦は一回ずつ
s.t. onceMatch{(t1,t2) in Match}: sum{(d,g) in GameIndex}assignGame[d,g,t1,t2]==1;
# 各チームの試合は1日以下
s.t. restrictGameTime{d in Date, t in Team}: sum{(d,g) in GameIndex, (t1,t2) in Match: t1==t or t2==t}assignGame[d,g,t1,t2]<=1;
# 時間帯を分散させる、同じ試合番号では各チーム2回まで
s.t. restrictGame{t in Team, g in GameNumber}: sum{(d,g) in GameIndex, (t1,t2) in Match: t1==t or t2==t}assignGame[d,g,t1,t2]<=2;
# 試合をする時間の処理
s.t. fix_game{(d,g,t) in fixGameSchedule}: sum{(t1,t2) in Match: t1==t or t2==t}assignGame[d,g,t1,t2]==1;
# 試合を避ける時間の処理
s.t. avoid_game{(d,g,t) in avoidGameSchedule}: sum{(t1,t2) in Match: t1==t or t2==t}assignGame[d,g,t1,t2]==0;

solve;
# 出力
printf{(d,g) in GameIndex, (t1,t2) in Match : assignGame[d,g,t1,t2]==1} "%d   %d   %d - %d\n", d, g, t1, t2;

data;
# チーム数
param nTeam := 7;
# 日付とその日の試合数
param : Date : nGame :=
1    3
2    3
3    3
4    3
5    3
6    3
7    3
;
# 試合をする日付、試合番号、チーム
set fixGameSchedule :=
(1, 1, *) 1 2
(1, 2, *) 3 4
(1, 3, *) 5 6
;
# 試合を避ける日付、試合番号、チーム
set avoidGameSchedule :=
(1, *, 7) 1 2 3
(2, *, 6) 1 2 3
(3, *, 5) 1 2 3
(4, *, 4) 1 2 3
(5, *, 3) 1 2 3
(6, *, 2) 1 2 3
(7, *, 1) 1 2 3
;