テニス大会のタイムテーブルのプログラミングについて

質問

テニス大会の乱数表（プログラミング）作成をお手伝いいただけませんか？

大会開催に関して、下記の比較的、複雑な条件下で大会を運営しています。
そこでテニス大会の乱数表（プログラミング）作成していただける方を探しています。

対戦表（～班～ペア vs ～班～ペア）×（85～100試合）
はこちらで作成いたします。

そこで、それらの試合を
以下の(1)～(17)の条件を満たしたうえで
試合投入できるようなスケジュール（順番と枠組みのみでＯＫ）
を組めるプログラムを探しております。こちらOSはウインドウズ７です。

---------条件は以下です--------

(1)「３日」で完了する「ダブルス」のテニス大会
総人数は５５～７０名程のメンバーが、
あらかじめ「4つの班」 に分かれ、人数はほぼ均等に振り分けられている。
ここでは（o班、j班、n班、y班とする）

(2)班内でペアを作り、他班のペアとダブルスの試合する。
一人あたりの試合数がおおよそ６試合前後になるように私が組んでいるが、
各人の試合数はその人によって異なる。
（大会の総試合数はおおよそ８０～１００試合ぐらい）
レベル別に近い者同士がペアを組んで、他の班のおおよそ同レベルの相手と試合できるように事前に組んでいる。
なので、すべての対戦内容は（班内でのペアと、 その対戦相手の組み合わせ）は予め決まっているし、
各々の試合内容は大会内での他の試合の結果から変動することはない。

(3)大会プログラムは１日目、２日目、３日目ともに
・朝A （３試合）
・朝B （６～８試合）
・朝C （４試合）
・昼A （３試合）
・昼B （９～１２試合）
・夜A （２試合）
以上のような予定で行うとする。

(4)コートについては、頃合いをみて運営スタッフが空いたコートに試合をコールする。
ゆえに最大のコート数や、コート番号はここでは無視する。

(5)３日目は、１、２日目のどちらよりも少ない試合数であるとする。
また、１日目と２日目の試合数の差は最大３つまでとする。

(6)１人が一日分として試合できる数は１～３試合である。
０試合と4試合以上は不可能とする。

(7)朝A,Bでの試合を禁止される人もいる。各人について入力欄を設け制約の変更がきくようにしたい

(8)一日分で３試合行うことがが禁止される人もいる。各人について入力欄を設け制約の変更がきくようにしたい

(9)個々人にについて
試合間隔は「自分の入っていない６試合」 を空けなければ次の試合に入ってはならない。
「6試合分の時間」ではなく「必ず6試合あける」こととする。
この条件(9)は日にちごとに有効だが、日は跨がない。

(10)「朝A、昼A、夜A」 の（２試合または３試合）は、条件(9)の試合間隔を計算する際には、
まとめて１試合分としてでカウントする

例えば、、、
・（朝A-1～朝A-3）のいずれかの試合に出場した選手は6試合の間隔をあけるため、
（朝B‐1 ～ 朝B-6）には出場できない。

・朝C－４に出場した選手は6試合の間隔をあけるため、
（昼A-1～昼A-3、昼B-１～昼B-５）には出場できない。

(11)夜Aで対戦を行うペアとその対戦相手ペアは初めから決まっていて固定である。
配置・内容は変動しない試合だが、試合出場者はその他の条件の対象としてカウントされる試合である。

(12)ある試合が「その試合の参加者（4名のうちの誰か1人、もしくは２～４人で複数の可能性もある）にとっての、
その大会内での最後の試合」となるように設定しなければならないことがある。
例えば、一人あたり６試合行う人がいたとしたら、その人にとって必ず６番目に持ってこなければならない試合
が存在する可能性がある。

(13)（ｎ班のペア ｖｓ ｙ班のペア）による対戦が３つ以上連続してはならない。
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班同士についても同様とする。
ただし夜Aの試合については考慮しない

(14)ｎ班全体で見たときに、 ｙ班のペアとの対戦が一日分の試合の半分以上を占めてはならない 。
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班同士についても同様とする。

(15)もし3日間の大会ではなく、 2日間の大会だと総試合数は60試合程度になる。
その場合、２日目の試合数が１日目より多くなってはいけない。

(16)大会が２日間のときでも、(1)～(17)を満たすスケジュールを出力できるプログラミングの仕様だと望ましい。
3日間用と2日間用が別々になっても大丈夫です。

(17)出力される3日間のスケジュールは以上の条件を満たす、ランダムに1パターンないしは、全パターンの出力が望ましい。

-------------条件は以上ですーーーーーーーーーーーーーー

８月31日の大会に間に合わせたいと考えています。
が、難しい場合については
(12)(13)(14)(15)の条件については,
手作業で満たしているかどうか確認を行うので省いても大丈夫です。

回答No.22

ki073

お役にたてたようで何よりです。

>余談ですが、やはり予想通り怪我人が多くいたため、いくつも条件を変更できる仕様で本当に助かりました。

日程への割り付けの方は、そこまでは考えていなかったのですが、スムーズにできましたでしょうか？
実際には使ってみないと分からない事がいろいろある思いますので、こんな機能があれば良かったのにと思う事がありましたら、書き込んでください。簡単にできることでしたらこの際修正します。

また、この機能が便利だったいうこともあれば書き込んでください。

GLPK は整数計画法という数学分野のものですし、経済学分野のOR(オペレーションリサーチ)など利用されているものです。このような分野に興味のある人を騙して？勉強させてみてください。そうすれば自分たちで改良しながずっと使い続けることができます。

回答No.21

ki073

No.20の補足欄について
「補足欄」に書かれた場合はここに見にこないと書かれたことが知ることができません、「お礼欄」の場合は回答者にメールがきますので。可能な限り「お礼欄」でお願いします。たまたま気になって見に来たので気がついたのです。

さて、今の条件では(n,y)→(n,y) →(n,j)→(n,j)はOKとなっています。
要するに(n,y)の組み合わせが3回連蔵しない条件と解釈しました。(n,j)は別の組み合わせと判断しています。
質問者さんは、同じグループの人(ここではn班)が4回続かないということのようですね。

# 同じグループが4回連続しない、夜は含めない
param MatchPairID_Group{mp in MatchPairIDSet, group in GroupSet} binary :=
if exists{i in 1..4}(AssignedGroup[Players[mp, i]]=group) then 1 else 0;
var MatchScheduleID_Group_table{MatchScheduleIDSet, GroupSet} binary;
s.t. update_MatchScheduleID_Group_table{ms in MatchScheduleIDSet, group in GroupSet}:
sum{mp in MatchPairIDSet: MatchPairID_Group[mp, group]=1}MatchScheduleID_MatchPairID_table[ms,mp]=MatchScheduleID_Group_table[ms, group];
s.t. group_exception4{ms in StartMatchID+3..EndMatchID-nMatchesNight, group in GroupSet}:
sum{k in 0..3}MatchScheduleID_Group_table[ms-k, group]<=3;
を
# 同じグループの組み合わせが3回連続しない 夜は含めない
の行の前に追加してください。条件が追加されます。

「同じグループの組み合わせが3回連続しない」の条件が必要ないなら
その次の2行
s.t. group_exception{ms in group_exception3, (group1, group2) in GroupPairofMatches}:
sum{k in 0..2}MatchScheduleID_Group2_table[ms-k, group1, group2]<=2;
をコメントにしておいてください。
それぞれの行の頭に#を追加するか、/*と*/で挟むとその間（複数行）がコメントになります。

お礼

遅くなりましたが、無事大会を終えることができました。

本当に感謝しております。
余談ですが、やはり予想通り怪我人が多くいたため、いくつも条件を変更できる仕様で本当に助かりました。
プログラムの効果は十二分に発揮することができたと思います。

いつも複数人の運営スタッフが夜通しで考えているような我々とって革命的なプログラムとなったことは間違いありません。
とあるテニスサークルという規模ではありますが、これからも着実に伝え残し、受け継がれるものにしていこうと思います。

重ね重ねではありますが、
本当にありがとうございましたm(_ _)m

回答No.20

ki073

こちらもデータ領域だけの書き換えで可能です。
対戦データは先のプログラムの出力の一部をそのままコピペで使えます。
この質問は作業が終わるまで閉め切らないでください。
ご存知だと思いますが、プログラムの実行はcontrolキーを押したままcキーを押すと止まります（Windowsも多分）
こちらの方は朝ABを避ける試合が出来るだけ後ろになるような結果を出力します。
また先のものは各プレーヤーの試合日間の試合数ができるだけ同じになるようになるようにしています。
このデータでは第6試合から朝ABを避ける試合が入っていますので、もう少し試合日間の割当を変える必要がありそうです。

data;
param nMatchesAB := 5; # ABの試合数
param nMatchesMorning := 11; # 午前中の試合数
param nMatchesNight := 2; # 夜の試合数
## グループのリスト
set GroupSet := n o j y;
## Playerの所属するグループ
param : PlayerSet : AssignedGroup :=
N1 n
N2 n
N3 n
N4 n
N5 n
N6 n
N7 n
N8 n
N9 n
N10 n
N11 n
N12 n
N13 n
N14 n
N15 n
O1 o
O2 o
O3 o
O4 o
O5 o
O6 o
O7 o
O8 o
O9 o
O10 o
O11 o
O12 o
O13 o
O14 o
O15 o
J1 j
J2 j
J3 j
J4 j
J5 j
J6 j
J7 j
J8 j
J9 j
J10 j
J11 j
J12 j
J13 j
J15 j # J14からJ15に間違いを修正
Y1 y
Y2 y
Y3 y
Y4 y
Y5 y
Y6 y
Y7 y
Y8 y
Y9 y
Y10 y
Y11 y
Y12 y
Y13 y
Y14 y
Y15 y # 抜けていたため追加
;
## ABの試合に出られないPlayer名
set AvoidABPlayerSet :=
N1
N2
N3
N4
N5
O1
O2
O3
O4
O7
O12
J1
J2
J3
J4
J11
Y1
Y2
Y3
Y4
Y8
;
## 対戦番号とPlayer4人
param : MatchPairIDSet : Player1 Player2 Player3 Player4 :=
1 N1 N2 O1 O2 # (n : o) 朝AB避ける
3 N2 N4 O2 O4 # (n : o) 朝AB避ける
4 N3 N5 O3 O5 # (n : o) 朝AB避ける
11 N10 N11 O10 O11 # (n : o)
12 N12 N13 O12 O13 # (n : o) 朝AB避ける
13 N12 N14 O12 O14 # (n : o) 朝AB避ける
32 N1 N3 Y1 Y3 # (n : y) 朝AB避ける
35 N4 N6 Y4 Y6 # (n : y) 朝AB避ける
36 N5 N6 Y5 Y6 # (n : y) 朝AB避ける
37 N7 N8 Y7 Y8 # (n : y) 朝AB避ける
38 N7 N9 Y7 Y9 # (n : y)
39 N8 N9 Y8 Y9 # (n : y) 朝AB避ける
40 N10 N11 Y10 Y11 # (n : y)
45 N14 N15 Y14 Y15 # (n : y)
47 J1 J3 O1 O3 # (j : o) 朝AB避ける
50 J4 J6 O4 O6 # (j : o) 朝AB避ける
51 J5 J7 O5 O6 # (j : o)
52 J6 J8 O7 O8 # (j : o) 朝AB避ける
53 J7 J9 O7 O9 # (j : o) 朝AB避ける
54 J8 J9 O8 O9 # (j : o)
55 J10 J11 O10 O11 # (j : o) 朝AB避ける
60 J13 J15 O14 O15 # (j : o)
76 J1 J2 Y1 Y2 # (j : y) 朝AB避ける
78 J2 J4 Y3 Y4 # (j : y) 朝AB避ける
79 J3 J5 Y2 Y5 # (j : y) 朝AB避ける
86 J10 J11 Y10 Y11 # (j : y) 朝AB避ける
87 J12 J13 Y12 Y13 # (j : y)
88 J12 J15 Y12 Y14 # (j : y)
;
# 試合を特定の試合番号に指定
# 対戦番号 試合番号の範囲（始め、終わり）
param : FixedMatchPairID : FixedMatchRangeStart FixedMatchRangeEnd :=
79 27 28 # 夜の試合の範囲27～28
3 27 28
1 20 26 # 昼最後の7試合に設定することで最終出場に必ずなる
52 20 26
11 20 26
87 20 26
;
end;

お礼

まずは、ここまでのプログラムを作っていただいたこと、ありがとうございます。

ただいま運用についての試行錯誤（データからの条件の調節）を行っております。

・条件を縮めすぎたり、辻褄が合わなくなると、パターンがなくなりエラーがでる。
かといって　
・条件が緩すぎると、パターンが多く、出力に時間がかかる。
ということでしょうかね。

第１段階の振り分けプログラムに関してですが、
さらに振り分ける材料を考えたところ、班ごとの対戦傾向に偏りをできるだけなくしたいと思いました。
そこで、今までは　（ある班　対　ある班　の割合の限界を５０パーセント）としていましたが
これを（２０パーセント）にまで下げることでかなり時間を絞ることができました。
おまけに各対戦班にも隔たりがなくなりましたので結果的に一石二鳥となりました。

第二段階の、並び替えについては仰るとおりにするしかないようです。
朝ＡＢの試合数をいじり、あとはどの試合をどのあたりに入れるのかをおおよそ決めておけば、
出力しやすそうです。

正直、ここまで融通の利く内容であれば、むしろ多少の条件の手作業は当然と考えるしかないですね。

お世話になりすぎて、感謝してもしきれないほどのものでございます。

実際に大会で運用できるまでこの質問は残す予定ですので
また何か疑問点等ございましたら恐縮ながら書き込むかもしれません。
本当に本当に、ありがとうございます。

補足

非常に恐縮なのですが、訂正した条件の検討をお願いしたいのです。
というのも、少し私の条件提示の表現にミスがありました。

条件(13)についてを訂正したく思っています。

今までは
(13)（ｎ班のペア ｖｓ ｙ班のペア）による対戦が３つ以上連続してはならない。
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班同士についても同様とする。
ただし夜Aの試合については考慮しない

としていましたが、
これを以下に変更したいのです。

(13)（ｎ班のペア）が参加している対戦が４つ以上連続してはならない。
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班についても同様とする。
ただし夜Aの試合については考慮しない

例えば・・・

（ｎ班　VS　ｙ班）→（ｏ班　VS　ｎ班）→（ｎ班　VS　ｊ班）→（ｎ班　VS　ｊ班）
という試合投入の順だと、ｎ班が４回連続で出場しているため、条件を満たしていないとみなす。

ということで、
今あるプログラムの一部（条件(13)の部分）を書き換えることで
上手く対応することはできるのでしょうか？

回答No.19

ki073

# MatchScheduleID_Player_tableを書き換え
s.t. update_MatchScheduleID_Player_table{ms in MatchScheduleIDSet, py in PlayerSet}:
sum{mp in MatchPairIDSet : MatchPairID_Player[mp, py]=1}MatchScheduleID_MatchPairID_table[ms,mp]=MatchScheduleID_Player_table[ms, py];
# ABに試合ができないPlayerの処理
s.t. avoidAB{ms in MatchScheduleIDAB, py in AvoidABPlayerSet}: MatchScheduleID_Player_table[ms ,py]=0;

# MatchScheduleID_Group2_tableを書き換え
s.t. update_MatchScheduleID_Group2_table{ms in MatchScheduleIDSet, (group1, group2) in GroupPairofMatches}:
sum{mp in MatchPairIDSet: MatchPairID_Group2[mp, group1, group2]=1}MatchScheduleID_MatchPairID_table[ms,mp]=MatchScheduleID_Group2_table[ms, group1, group2];
s.t. uniq_group{ms in MatchScheduleIDSet}: sum{(group1, group2) in GroupPairofMatches}MatchScheduleID_Group2_table[ms, group1, group2]=1;

# 同じグループの組み合わせが3回連続しない 夜は含めない
s.t. group_exception{ms in group_exception3, (group1, group2) in GroupPairofMatches}:
sum{k in 0..2}MatchScheduleID_Group2_table[ms-k, group1, group2]<=2;

# 連続した9試合中1試合以下であること
s.t. one_or_zero_in_9_matches{ms in check_9_matches, py in PlayerSet}:
sum{k in 0..8}MatchScheduleID_Player_table[ms-k, py]<=1;
# 連続した8試合中1試合以下であること
s.t. one_or_zero_in_8_matches{ms in check_8_matches, py in PlayerSet}:
sum{k in 0..7}MatchScheduleID_Player_table[ms-k, py]<=1;
# 連続した7試合中1試合以下であること
s.t. one_or_zero_in_7_matches{ms in check_7_matches, py in PlayerSet}:
sum{k in 0..6}MatchScheduleID_Player_table[ms-k, py]<=1;
solve;
# 出力
for{(group1, group2) in GroupPairofMatches}
{printf "# %s : %s %s 試合\n", group1, group2, sum{mp in MatchPairIDSet}MatchPairID_Group2[mp, group1, group2];}
for{ms in MatchScheduleIDSet}
{for {mp in MatchPairIDSet : MatchScheduleID_MatchPairID_table[ms, mp]=1}
{printf "%s %s %s %s %s %s (%s : %s) %s\n", ms, mp, Player1[mp], Player2[mp], Player3[mp], Player4[mp],
AssignedGroup[Player1[mp]], AssignedGroup[Player3[mp]],
if mp in avoidABMatchPairIDSet then " 朝ABを避ける試合" else "";}
}

回答No.18

ki073

一日の作成するものも書き込んでおきます
# 一日のスケジュールを作成
param nMatchesAB; # ABの試合数
param nMatchesMorning; # 午前中の試合数
param nMatchesNight; # 夜の試合数

set MatchPairIDSet; # 対戦番号の集合
set MatchScheduleIDSet := 1..card(MatchPairIDSet); # 試合番号の集合
param StartMatchID := 1; # 開始試合番号
param EndMatchID := card(MatchPairIDSet); # 最終試合番号
param StartMatchIDofAfternoon := StartMatchID+nMatchesMorning; # 午後の開始試合番号

set GroupSet; # グループ名の集合
set PlayerSet; # Player名の集合
set AvoidABPlayerSet; # ABの試合ができないPlayerの集合
set GroupPairofMatches := {group1 in GroupSet, group2 in GroupSet: group1<group2};
set FixedMatchPairID; # 試合番号が決っている対戦番号
param FixedMatchRangeStart{FixedMatchPairID};
param FixedMatchRangeEnd{FixedMatchPairID};
set FixedMatchRange{mp in FixedMatchPairID} := FixedMatchRangeStart[mp]..FixedMatchRangeEnd[mp]; # 試合を設定する試合番号の範囲

param AssignedGroup{PlayerSet} symbolic; # Playerとその所属グループ
param Player1{MatchPairIDSet} symbolic; # 対戦番号とPlayer
param Player2{MatchPairIDSet} symbolic;
param Player3{MatchPairIDSet} symbolic;
param Player4{MatchPairIDSet} symbolic;
param Players{mp in MatchPairIDSet, i in 1..4} symbolic := # 配列に
if i=1 then Player1[mp] else
if i=2 then Player2[mp] else
if i=3 then Player3[mp] else Player4[mp];
# Player1とPlayer2,Player3とPlayer4同じグループかチェック
check{mp in MatchPairIDSet}: AssignedGroup[Players[mp, 1]]=AssignedGroup[Players[mp, 2]];
check{mp in MatchPairIDSet}: AssignedGroup[Players[mp, 3]]=AssignedGroup[Players[mp, 4]];
# 同じグループ間の対戦は無いかチェック
check{mp in MatchPairIDSet}: AssignedGroup[Players[mp, 1]]<>AssignedGroup[Players[mp, 3]];
# 対戦番号とPlayer名の対応表
param MatchPairID_Player{mp in MatchPairIDSet, py in PlayerSet} binary :=
if exists{i in 1..4}(Players[mp, i]=py) then 1 else 0;
# 対戦番号とグループ名の対応表
param MatchPairID_Group2{mp in MatchPairIDSet, (group1, group2) in GroupPairofMatches} binary :=
if (AssignedGroup[Players[mp, 1]]=group1 and AssignedGroup[Players[mp, 3]]=group2) or
(AssignedGroup[Players[mp, 3]]=group1 and AssignedGroup[Players[mp, 1]]=group2) then 1 else 0;
# 試合でPlayerが重複していないかチェック
check{mp in MatchPairIDSet}: sum{py in PlayerSet}MatchPairID_Player[mp, py]=4;
# 朝ABに出場できないPlayerがいる対戦番号
set avoidABMatchPairIDSet := {mp in MatchPairIDSet : exists{py in AvoidABPlayerSet}MatchPairID_Player[mp, py]=1};
param coefficients{mp in avoidABMatchPairIDSet} := round(Uniform(100, 150)); # 高速化のため優先度をランダムに指定

# 個人別の試合数を出力
printf "Player Group 試合数\n";
for{py in PlayerSet}
{printf "%s %s %d\n", py, AssignedGroup[py], sum{mp in MatchPairIDSet}MatchPairID_Player[mp, py];}
# 試合へ出る間隔のための準備
# その試合と前8試合中で1回出場できる、朝第9試合、昼第3～第9試合
set check_9_matches := {StartMatchID+8} union
StartMatchIDofAfternoon+2..StartMatchIDofAfternoon+8;
# その試合と前7試合中で1回出場できる、昼第2試合
set check_8_matches := {StartMatchIDofAfternoon+1} ;
# その試合と前6試合中で1回出場できる、その他
set check_7_matches := StartMatchID+9..EndMatchID;
# 試合ABの範囲
set MatchScheduleIDAB := StartMatchID..nMatchesAB-1;
# 各試合日の第3試合から夜の試合の前までの範囲、グループの連続性を調べるために使う
set group_exception3 := StartMatchID+2..EndMatchID-nMatchesNight;

var MatchScheduleID_MatchPairID_table{MatchScheduleIDSet, MatchPairIDSet} binary;
var MatchScheduleID_Group2_table{MatchScheduleIDSet, GroupPairofMatches} binary;
var MatchScheduleID_Player_table{MatchScheduleIDSet, PlayerSet} binary;

s.t. uniq_MatchPairID{ms in MatchScheduleIDSet}: sum{mp in MatchPairIDSet}MatchScheduleID_MatchPairID_table[ms, mp]=1;
s.t. uniq_MatchScheduleID{mp in MatchPairIDSet}: sum{ms in MatchScheduleIDSet}MatchScheduleID_MatchPairID_table[ms, mp]=1;

# 朝ABを避けるplayerの試合をできるだけ後ろになるように
maximize lateScheduleforAviodABMembers:
sum{ms in MatchScheduleIDSet, mp in avoidABMatchPairIDSet}MatchScheduleID_MatchPairID_table[ms, mp]*coefficients[mp]*ms*ms;

# 試合番号が決められている試合
s.t. fixmatch{mp in FixedMatchPairID}: sum{ms in FixedMatchRange[mp]}MatchScheduleID_MatchPairID_table[ms, mp]=1;

回答No.17

ki073

データ部分で、3つを全部つなげて使ってください。
data部分だけの変更で、何日でも対応できます。試合数は手で設定してください。条件に合わない設定だとすぐに止まりますので、一つずつ修正しないがら入れていくのが早いです。
主な設定は後ろの方に有り、試合日を固定、その日を避ける、同じ日、違う日に試合をするなどの設定ができます。
試行錯誤していくしか無いようですので、いろいろ設定しやすいことを優先しました。
このデータでは3分くらいで結果はでますが、条件を追加すると、候補がだんだん少なくなってくるので早くなります。
それといろいろ集計結果がでますので、手でやるよりは便利になっているのでは無いかと思いますが、どうでしょうか。
朝ABに出られない人は試合上限を2として追加しています(#じるしがある)
それと#から後はコメントですので、データを外したりするのに使ってみてください。
もう一つ、セミコロン(;)は区切りとして重要ですので、取ったり付けたりするとエラーになりますので注意してください。
# ------------
data;
## 試合日 その日の試合数
param : DateSet : nMatches :=
1 31
2 31
3 28
;
## グループのリスト
set GroupSet := n o j y;
## Playerの所属するグループ
param : PlayerSet : AssignedGroup :=
N1 n
N2 n
N3 n
N4 n
N5 n
N6 n
N7 n
N8 n
N9 n
N10 n
N11 n
N12 n
N13 n
N14 n
N15 n
O1 o
O2 o
O3 o
O4 o
O5 o
O6 o
O7 o
O8 o
O9 o
O10 o
O11 o
O12 o
O13 o
O14 o
O15 o
J1 j
J2 j
J3 j
J4 j
J5 j
J6 j
J7 j
J8 j
J9 j
J10 j
J11 j
J12 j
J13 j
J15 j # J14からJ15に間違いを修正
Y1 y
Y2 y
Y3 y
Y4 y
Y5 y
Y6 y
Y7 y
Y8 y
Y9 y
Y10 y
Y11 y
Y12 y
Y13 y
Y14 y
Y15 y # 抜けていたため追加
;
## 一日の最高試合数が標準と異なるPlayerと試合数
param UpperLimit :=
N1 2
N2 2 #
N3 2 #
N4 2
N5 2
O1 2
O2 2 #
O3 2 #
O4 2
O6 2
O7 2
O12 2 #
J1 2
J2 2
J3 2
J4 2 #
J11 2 #
Y1 2
Y2 2
Y3 2 #
Y4 2
Y8 2 #
;
## 一日の最低試合数が標準と異なるPlayerと試合数
param LowerLimit :=
;
## ABの試合に出られないPlayer名
set AvoidABPlayerSet :=
N1
N2
N3
N4
N5
O1
O2
O3
O4
O7
O12
J1
J2
J3
J4
J11
Y1
Y2
Y3
Y4
Y8
;
## 対戦番号とPlayer4人
param : MatchPairIDSet : Player1 Player2 Player3 Player4 :=
1 N1 N2 O1 O2
2 N1 N3 O1 O3
3 N2 N4 O2 O4
4 N3 N5 O3 O5
5 N4 N5 O4 O5
6 N6 N7 O6 O7
7 N6 N8 O6 O8
8 N7 N8 O7 O8
9 N9 N10 O9 O10
10 N9 N11 O9 O11
11 N10 N11 O10 O11
12 N12 N13 O12 O13
13 N12 N14 O12 O14
14 N13 N15 O13 O15
15 N14 N15 O14 O15
16 N1 N2 J1 J2
17 N1 N4 J1 J4
18 N2 N3 J2 J3
19 N3 N4 J3 J4
20 N5 N6 J5 J6
21 N5 N7 J5 J7
22 N6 N7 J6 J7
23 N8 N9 J8 J9
24 N8 N10 J8 J10
25 N9 N10 J9 J10
26 N11 N12 J10 J11
27 N11 N13 J11 J12
28 N12 N15 J11 J13
29 N13 N14 J12 J15
30 N14 N15 J13 J15
31 N1 N2 Y1 Y2
32 N1 N3 Y1 Y3
33 N2 N3 Y2 Y3
34 N4 N5 Y4 Y5
35 N4 N6 Y4 Y6
36 N5 N6 Y5 Y6
37 N7 N8 Y7 Y8
38 N7 N9 Y7 Y9
39 N8 N9 Y8 Y9
40 N10 N11 Y10 Y11
41 N10 N12 Y10 Y12
42 N11 N12 Y11 Y12
43 N13 N14 Y13 Y14
44 N13 N15 Y13 Y15
45 N14 N15 Y14 Y15
46 J1 J2 O1 O2
47 J1 J3 O1 O3
48 J2 J3 O2 O3
49 J4 J5 O4 O5
50 J4 J6 O4 O6
51 J5 J7 O5 O6
52 J6 J8 O7 O8
53 J7 J9 O7 O9
54 J8 J9 O8 O9
55 J10 J11 O10 O11
56 J10 J12 O10 O12
57 J11 J15 O11 O12
58 J12 J13 O13 O14
59 J13 J15 O13 O15
60 J13 J15 O14 O15
61 Y1 Y2 O1 O2
62 Y1 Y4 O1 O4
63 Y2 Y3 O2 O3
64 Y3 Y4 O3 O4
65 Y5 Y6 O5 O6
66 Y5 Y7 O5 O7
67 Y6 Y7 O6 O7
68 Y8 Y9 O8 O9
69 Y8 Y10 O8 O10
70 Y9 Y10 O9 O10
71 Y11 Y12 O11 O12
72 Y11 Y13 O11 O13
73 Y12 Y15 O12 O15
74 Y13 Y14 O13 O14
75 Y14 Y15 O14 O15
76 J1 J2 Y1 Y2
77 J1 J3 Y1 Y3
78 J2 J4 Y3 Y4
79 J3 J5 Y2 Y5
80 J4 J5 Y4 Y5
81 J6 J7 Y6 Y7
82 J6 J8 Y6 Y8
83 J7 J8 Y7 Y8
84 J9 J10 Y9 Y10
85 J9 J10 Y9 Y11
86 J10 J11 Y10 Y11
87 J12 J13 Y12 Y13
88 J12 J15 Y12 Y14
89 J13 J15 Y13 Y15
90 J12 J15 Y14 Y15
;
# 特定の日に試合を設定
# 対戦番号 試合日
param : FixMatchIDSet : FixMatchDate :=
31 1
46 1
61 2
16 2
79 3
3 3
1 3
52 3
11 3
87 3
50 3
51 3
10 1
15 2
;
# 特定の日に試合を避けたい設定
# 対戦番号 試合日
param : AvoidMatchIDSet : AvoidMatchDate :=
;
# 同じ日に開催する試合
# 通し番号 対戦番号1 対戦番号2
param : MatchinSameDaySerial : MatchinSameDay1 MatchinSameDay2 :=
1 61 62
2 61 63
3 76 78
;
# 違う日に開催する試合
# 通し番号 対戦番号1 対戦番号2
param : MatchinOtherDaySerial : MatchinOtherDay1 MatchinOtherDay2 :=
1 46 47
2 47 48
3 76 77
;
end;

回答No.16

ki073

続きです。

s.t. otherdayMatch{day in DateSet, i in MatchinOtherDaySerial}:
Date_MatchPairID_table[day, MatchinOtherDay1[i]]+Date_MatchPairID_table[day, MatchinOtherDay2[i]]<=1; # 違う日開催

# Date_Player_tableを書き換え
s.t. update_Date_Player_table{day in DateSet, py in PlayerSet}:
sum{mp in MatchPairIDSet : MatchPairID_Player[mp, py]=1}Date_MatchPairID_table[day,mp]=Date_Player_table[day, py];

# 一日の試合数制限
s.t. limit1s{py in PlayerSet, day in DateSet}: LowerLimit[py]<= Date_Player_table[day, py];
s.t. limit1u{py in PlayerSet, day in DateSet}: Date_Player_table[day, py] <=UpperLimit[py];

# Date_Group2_tableを書き換え
s.t. update_Date_Group2_table{day in DateSet, (group1, group2) in GroupPairofMatches}:
sum{mp in MatchPairIDSet: MatchPairID_Group2[mp, group1, group2]=1}Date_MatchPairID_table[day,mp]=Date_Group2_table[day, group1, group2];
# グループの同じ組み合わせが対戦の50%以下
s.t. limit_sama_group_pair{day in DateSet, (group1, group2) in GroupPairofMatches}:
Date_Group2_table[day, group1, group2]<=nMatches[day]*0.5;

solve;
# 結果出力
printf "Playerの試合日別試合数\n";
for {py in PlayerSet}
{printf "%s ", py;
for{day in DateSet}{printf " %d", Date_Player_table[day, py];}
printf " %d\n", sum{day in DateSet}Date_Player_table[day, py];}
printf "対戦の試合日割当表\n";
for{mp in MatchPairIDSet}
{printf "%s %s\n", mp, sum{day in DateSet : Date_MatchPairID_table[day, mp]=1}day;}
printf "試合日ごとの対戦表\n";
for{day in DateSet}
{printf "# 試合日 %s\n", day;
for{(group1, group2) in GroupPairofMatches}{printf "# %s : %s %s 試合\n", group1, group2, Date_Group2_table[day, group1, group2];}
for {mp in MatchPairIDSet : Date_MatchPairID_table[day, mp]=1}
{printf "%s %s %s %s %s # (%s : %s) %s\n",
mp, Players[mp, 1], Players[mp, 2], Players[mp, 3], Players[mp, 4], AssignedGroup[Players[mp, 1]], AssignedGroup[Players[mp, 3]],
if exists{i in 1..4}(Players[mp, i] in AvoidABPlayerSet) then " 朝AB避ける" else " ";
}
}

回答No.15

ki073

試合の日程を振り分けるものを書き込みます。
set DateSet; # 試合日の集合
param nMatches{DateSet}; # 試合日ごとの試合数
set GroupSet; # グループ名の集合
set PlayerSet; # Player名の集合
set AvoidABPlayerSet; # 朝ABの試合ができないPlayerの集合
set FixMatchIDSet; # 特定の日に行う対戦
param FixMatchDate{FixMatchIDSet}; # 設定日
set AvoidMatchIDSet; # 特定の日に避けたい対戦
param AvoidMatchDate{AvoidMatchIDSet}; # 避けたい日
param AssignedGroup{PlayerSet} symbolic; # Playerとその所属グループ
set MatchPairIDSet; # 対戦番号
set MatchinSameDaySerial;
param MatchinSameDay1{MatchinSameDaySerial}; # 同日開催対戦
param MatchinSameDay2{MatchinSameDaySerial};
set MatchinOtherDaySerial;
param MatchinOtherDay1{MatchinOtherDaySerial}; # 違う日開催対戦
param MatchinOtherDay2{MatchinOtherDaySerial};

param Player1{MatchPairIDSet} symbolic; # 対戦番号とPlayer
param Player2{MatchPairIDSet} symbolic;
param Player3{MatchPairIDSet} symbolic;
param Player4{MatchPairIDSet} symbolic;
param Players{mp in MatchPairIDSet, i in 1..4} symbolic := # 配列に
if i=1 then Player1[mp] else
if i=2 then Player2[mp] else
if i=3 then Player3[mp] else Player4[mp];
param LowerLimit{PlayerSet} default 1; # 一日あたりの最低試合数
param UpperLimit{PlayerSet} default 3; # 最高試合数

param coefficients{py in PlayerSet} := round(Uniform(1000, 1500)+(if py in AvoidABPlayerSet then 2000 else 0)); # 優先度指定
set GroupPairofMatches := {group1 in GroupSet, group2 in GroupSet: group1<group2};
# 試合日ごとの試合数合計が全体の試合数と一致するか
check: sum{day in DateSet}nMatches[day]=card(MatchPairIDSet);
# Player1, Player2が同じグループかチェック
check{mp in MatchPairIDSet}: AssignedGroup[Players[mp, 1]]=AssignedGroup[Players[mp, 2]];
# Player3, Player4が同じグループかチェック
check{mp in MatchPairIDSet}: AssignedGroup[Players[mp, 3]]=AssignedGroup[Players[mp, 4]];
# 同じグループ間の対戦は無いかチェック
check{mp in MatchPairIDSet}: AssignedGroup[Players[mp, 1]]<>AssignedGroup[Players[mp, 3]];

# 対戦番号とPlayer名の対応表
param MatchPairID_Player{mp in MatchPairIDSet, py in PlayerSet} binary :=
if exists{i in 1..4}(Players[mp, i]=py) then 1 else 0;
# 対戦番号とグループ名の対応表
param MatchPairID_Group2{mp in MatchPairIDSet, (group1, group2) in GroupPairofMatches} binary :=
if (AssignedGroup[Players[mp, 1]]=group1 and AssignedGroup[Players[mp, 3]]=group2) or
(AssignedGroup[Players[mp, 3]]=group1 and AssignedGroup[Players[mp, 1]]=group2) then 1 else 0;
# 試合でPlayerが重複していないかチェック
check{mp in MatchPairIDSet}: sum{py in PlayerSet}MatchPairID_Player[mp, py]=4;
# 個人別の試合数を出力
printf "Player Group 総試合数\n";
for{py in PlayerSet}
{printf "%s %s %d\n", py, AssignedGroup[py], sum{mp in MatchPairIDSet}MatchPairID_Player[mp, py];}
# 対戦番号間でPlayer数の一致数
param PlayerCorrelation{mp1 in MatchPairIDSet, mp2 in MatchPairIDSet} :=
sum{py in PlayerSet}MatchPairID_Player[mp1, py]*MatchPairID_Player[mp2, py];

var Date_MatchPairID_table{DateSet, MatchPairIDSet} binary;
var Date_Group2_table{DateSet, GroupPairofMatches} integer >=0;
var Date_Player_table{DateSet, PlayerSet} integer >=0;

var T{PlayerSet} integer >=0;
minimize diffnMatches: sum{py in PlayerSet}T[py]*coefficients[py]; # 目的関数:Playerの試合数差が小さくなるように
s.t. diffnMatches1{py in PlayerSet, day1 in DateSet, day2 in DateSet: day1>day2}: Date_Player_table[day1, py]-Date_Player_table[day2, py]<=T[py];
s.t. diffnMatches2{py in PlayerSet, day1 in DateSet, day2 in DateSet: day1>day2}: -(Date_Player_table[day1, py]-Date_Player_table[day2, py])>=-T[py];

s.t. restrict_MatchPairID{day in DateSet}: sum{mp in MatchPairIDSet}Date_MatchPairID_table[day, mp]=nMatches[day]; # 日ごとの試合数
s.t. uniq_Date{mp in MatchPairIDSet}: sum{day in DateSet}Date_MatchPairID_table[day, mp]=1;

s.t. restrictMatchDay{mp in FixMatchIDSet}: Date_MatchPairID_table[FixMatchDate[mp], mp]=1; # 試合日が決っている場合
s.t. avoidMatchDay{mp in AvoidMatchIDSet}: Date_MatchPairID_table[AvoidMatchDate[mp], mp]=0; # 試合を避けたい日
s.t. samedayMatch{day in DateSet, i in MatchinSameDaySerial}:
Date_MatchPairID_table[day, MatchinSameDay1[i]]=Date_MatchPairID_table[day, MatchinSameDay2[i]]; # 同日開催

回答No.14

ki073

パズル大好きなのですが、かなり難しいパズルですね。
2つに分けたプログラム（とは言っても条件を並べただけの簡単なものですが）ができています。両方ともに実用的な時間で動くのですが、条件を満たす答えはないとつれない結果になります。どうも朝ABに出場できない人がの処理が足を引っ張っているいるようです。

朝ABに出場できない人を割り当てる時には何かコツがあるのでしょうか？それを入れておかないとかなりの試行錯誤が必要する。まずはこれをある程度解決しておかないと使えないような気がします。

これまでの一日分でも条件を満たすものがあれば書き込んでください。またコツがあったら教えてください。

最終的には完全自動化は無理で、並べ方についてはある程度人が関与が必要です。
手でやっていたのに比べれば遥かに時間短縮ができるものになっています。
要するに、試合をいつに割り当てるとか手でも指定でき、指定していないところは自動で割り当ててくれるものです。
条件を満たしているかは瞬時で判断してくれますので、かなりはかどると思います。上の朝ABに出れない人の試合割当を有る程度のメドがつけば使えるようになるのですが。

補足

朝Ａ，Ｂに出れない人の制限は今まで、
コツというよりかは、妥協できる範囲は妥協して成立させていたのが実情です。

緩和できそうな人は条件を解除して、朝Bに出場させることで何とか対応してきました。

※ここで提案なのですが「朝A、Bに不可」という条件から変更して

「（朝A、朝B-1、朝B-2、朝B-3）は出場不可」という条件
もしくは、「朝Aは出場不可」という条件

に条件を緩和してみるとどうなりますかね？

傾向としては
夜Aに出場する人たちは例外なく、朝A,Bの条件に引っかかりますので
条件そのものを緩和させる方向だとどうなるでしょうか？

サンプルについてはちょっと今用意できませんが、見つけ次第出してみようと思います
ご検討お願いします。

回答No.13

ki073

結構楽しんでやっております。
時々GLPKは使っていたのですが、前に書き込んだ様にいい加減なものでも今までは答えが出てきていたのですが、今回は結構複雑な条件ですので実用的な時間ではまだなようです。

任意の日単位（1日単位でもできるし、2日、3日、それ以上でも）並び替えができるのがほぼ完成しました。
前に書き込んだのを分かりやすい形に書き替えただけなのですが、副次的に出上がりました。

だいぶ速度は速くなってきましたが、3日間でやると何時間で答えがでるのかは分かりません。
ただし、条件を全てを満たす答えは無いよという返事は数秒で出てきます。現実的は条件の緩和をしないと無理なようです。

1) 昼A3試合を一ゲームとして時間を空けるが、昼休みを1ゲーム分として休憩にカウントできないか。
2) 朝Aも同時開始で一ゲームとしてカウントしますよね。
3）試合の間隔ですが、今は出場すると次の6ゲーム分を出場できないとしていますが、実際にはどうなのでしょうか？

今できているものは、特定の試合を何番目の試合から何番目の試合までの間にするか指定できます。
夜の試合と、最終試合を指定するために追加したのですが、これを利用して、何試合かを何日目の朝にやりたいとか、午後にやりたいなどをある程度していていくと速度的にはかなり速くなるように思います。
金曜日の夜でも、もう一度書き込みますので、実際にはどうするか考えましょう。まだ試してはいませんが、一日単位ではできそうな感じです。

お礼

続きです。勝手ながら、≪１≫≪２≫で分けるとする場合に
以前の条件を通し番号そのままに分けて、緩和できそうなところを緩和しました。
もし楽になりそうであればお返事いただけるとありがたいです。

見やすく省略した部分もありますが、大会の前提条件そのものはあまり変わっていません

【とくに変更してみた部分は※つけてます。】

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

≪１≫のプログラムに必要な条件

(1)参加者は「4つの班」 に分かれ（o班、j班、n班、y班とする）、
班内でペアを作り他班のペアとダブルスの試合する。
各人の試合数はその人によって異なる（１～3試合のどれか）

(3)大会プログラムは（１日あたり２５～３２試合）

・朝A （３試合）
・朝B （６～８試合）
・朝C （４試合）
・昼A （２～３試合）←※少し変更してますが、難しければ３に戻します
・昼B （８～１２試合）
・夜A （２試合）

(7)朝A,Bでの試合を禁止される人もいる。

(9)試合間隔は「自分の入っていない６試合」 を空けなければ次の試合に入ってはならない。

(10)「朝A、昼A、夜A」 の（２試合、３試合）は、条件(9)の試合間隔を計算する際には、
まとめて１試合分としてでカウント

例えば、、、
・（朝A-1～朝A-3）のいずれかの試合に出場した選手は6試合の間隔をあけるため、
（朝B‐1～朝B-6）には出場できない。

・朝C－４に出場した選手は6試合の間隔をあけるため、
（昼A-1～昼A-3、昼B-１～昼B-５）には出場できない。

(11)夜Aで対戦を行うペアとその対戦相手ペアは初めから決まっていてる。

(12)ある試合が、その中のある出場者にとっての、
※「その日における最後の試合」となるように設定しなければならない可能性がある。
その人がその日において2試合行うなら、必ず２番目になる試合のこと

(13)（ｎ班のペア ｖｓ ｙ班のペア）による対戦が３つ以上連続してはならない。←※４つ以上に緩和可能
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班同士についても同様とする。ただし夜Aの試合については考慮しない

(14)ｎ班全体で見たときに、 ｙ班のペアとの対戦が一日分の試合の半数以上を占めてはならない 。←※60％に緩和可能
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班同士についても同様とする。

(17)出力されるスケジュールは、ランダムに1パターン、または、エラー（満たすパターンなし。）

≪２≫のプログラムに必要な条件（あくまで《１》を優先ですが）

(1)「２～３日」で完了する「ダブルス」のテニス大会
メンバーが「4つの班」 に分かれ、班内でペアを作り他班のペアとダブルスの試合する。
ここでは（o班、j班、n班、y班とする）

(5)
※３日間の大会の時、各日にちの試合数はこちらで入力指定する※

３日目の試合数は、○○試合とする。
２日目は○○試合とする。
１日目は○○試合とする。

例：合計９０試合なら上から（２６－３２－３２）のように

また、これは２日間のときも同様である。

(6)１人が一日分として試合できる数は１～３試合のみ

(8)一日分で３試合行うことがが禁止される人もいる　←個人単位で緩和可

(12)※「3日目にのみ振り分けないといけない試合」がある。※
同様に「2日目に行う試合」、「1日目に行う試合」も存在する。

(14)ｎ班全体で見たとき、ｙ班のペアとの対戦が一日分の試合の半分以上を占めてはならない。（６割に緩和可能）
またこれは、（ｎ班,ｏ班,ｙ班,ｊ班） のすべての班同士についても同様とする。

(17)出力される3日間の振り分けは、ランダムに1パターン、ないしは、エラー

補足

お返事ありがとうございます。

まず件緩和の質問についてですが、非常に我儘な回答になってしまいますがご勘弁ください。

1) 昼A3試合を一ゲームとして時間を空けるが、昼休みを1ゲーム分として休憩にカウントできないか。
運営の都合上、昼休みとしてまとまった時間をとることができないのでカウントできそうにありません。。

2) 朝Aも同時開始で一ゲームとしてカウントしますよね。
はい。カウントいたします。

3）試合の間隔ですが、今は出場すると次の6ゲーム分を出場できないとしていますが、実際にはどうなのでしょうか？
実際にその通りです。最低6試合空けてから試合に入るよう運営しております。

ところで、先日のレスにも記載したのですが、

あまり苦労を掛けてしまうのもなんですし
まず前提として、１、２、３日目の試合振り分けはこちらで手作業で行うことにして

《１》「1日単位に限定した上で、（30試合程度を）並べ替えることのできるプログラム」

を教えていただくことは現状可能でしょうか？

その後に、もしご協力いただけるなら、
それとは別個に
《２》「(2)3日間（約90）の試合を３分割するのみのプログラム（スケジュールの並び替えは不要）」
というものにするのではいかがでしょう。

プログラムそのものは２種類作成することになりそうですが、
その方が時間効率はよさそうに感じましたが実際のところはいかがでしょう？
素人感覚になってしまい恐縮です。

もし《１》《２》の２つのプログラム作成にするとすれば、
今ある条件は《１》用と《２》用で、2分割に整理してお伝えした方がわかりやすいでしょうか？
基本的な条件そのものはあまり変更はないかとは思われますが、必要なもの、不必要なものはそれぞれあるかと思いますので。