３人対戦ゲームの試合数・対戦表　／　組み合わせ（数え上げ）問題を線形計画問題ソルバ GLPK を使って解く

2021/07/29 19:01 整数計画問題
数学(大学の教養科目)でこんな問題がありました（文章は変えてあります）。
・３人で行うゲームがある
・９人が参加する
・各プレイヤーは４回だけプレイできて、さらに他のすべてのプレイヤーとちょうど１回ずつプレイする
・このような条件をみたすゲームの個数（＝試合数）は何通りあるか、対戦表は作れるか
数え上げ問題なのですが、この問題を整数計画問題として（もともと数え上げ問題だったものを整数計画問題に「擬態」して、それ用のソルバで解けるようにして） GLPK (Gnu Linear Programming Kit) を使って解いてみたので、これで正解なのか自信がありませんが（なんだか A+ の成績はいただけたけど、正解したとは限らないし・・・、コロナ禍のもと対面授業ではなかったので質問の機会がなかったのです）、私なりの解答を披露したいと思います。

＃Yahoo!知恵袋 でも、同じ問題の答えを聞いている人がいました（こちら や こちら）。
＃前者の回答例は、私の解答での m02,m12,m22,m23,m30,m46,m47,m51,m63,m66,m74,m76 パターンで、対戦表では No. 352 にあたります。
＃似てるけどちょっと違う出題に、数学の部屋『３人ゲームのリーグ戦』の「問題１」があります。

途中、GLPK を何百回も繰り返して実行する箇所がありますので、そういうところは perl スクリプトで自動実行しています。

答案

まず、９人に１，２，３，・・・，９と番号を付ける。
９人のうち３人でゲームをするから、その組み合わせは {}_9 \mathrm{C}_3 で、８４通りある。
この組み合わせにも番号を付け、それぞれ m01, m02, ..., m84 と表す。
一覧は次の通り。
表１ 対戦のパターン
m01[1 x 2 x 3]m29[2 x 3 x 4]m57[3 x 5 x 8]
m02[1 x 2 x 4]m30[2 x 3 x 5]m58[3 x 5 x 9]
m03[1 x 2 x 5]m31[2 x 3 x 6]m59[3 x 6 x 7]
m04[1 x 2 x 6]m32[2 x 3 x 7]m60[3 x 6 x 8]
m05[1 x 2 x 7]m33[2 x 3 x 8]m61[3 x 6 x 9]
m06[1 x 2 x 8]m34[2 x 3 x 9]m62[3 x 7 x 8]
m07[1 x 2 x 9]m35[2 x 4 x 5]m63[3 x 7 x 9]
m08[1 x 3 x 4]m36[2 x 4 x 6]m64[3 x 8 x 9]
m09[1 x 3 x 5]m37[2 x 4 x 7]m65[4 x 5 x 6]
m10[1 x 3 x 6]m38[2 x 4 x 8]m66[4 x 5 x 7]
m11[1 x 3 x 7]m39[2 x 4 x 9]m67[4 x 5 x 8]
m12[1 x 3 x 8]m40[2 x 5 x 6]m68[4 x 5 x 9]
m13[1 x 3 x 9]m41[2 x 5 x 7]m69[4 x 6 x 7]
m14[1 x 4 x 5]m42[2 x 5 x 8]m70[4 x 6 x 8]
m15[1 x 4 x 6]m43[2 x 5 x 9]m71[4 x 6 x 9]
m16[1 x 4 x 7]m44[2 x 6 x 7]m72[4 x 7 x 8]
m17[1 x 4 x 8]m45[2 x 6 x 8]m73[4 x 7 x 9]
m18[1 x 4 x 9]m46[2 x 6 x 9]m74[4 x 8 x 9]
m19[1 x 5 x 6]m47[2 x 7 x 8]m75[5 x 6 x 7]
m20[1 x 5 x 7]m48[2 x 7 x 9]m76[5 x 6 x 8]
m21[1 x 5 x 8]m49[2 x 8 x 9]m77[5 x 6 x 9]
m22[1 x 5 x 9]m50[3 x 4 x 5]m78[5 x 7 x 8]
m23[1 x 6 x 7]m51[3 x 4 x 6]m79[5 x 7 x 9]
m24[1 x 6 x 8]m52[3 x 4 x 7]m80[5 x 8 x 9]
m25[1 x 6 x 9]m53[3 x 4 x 8]m81[6 x 7 x 8]
m26[1 x 7 x 8]m54[3 x 4 x 9]m82[6 x 7 x 9]
m27[1 x 7 x 9]m55[3 x 5 x 6]m83[6 x 8 x 9]
m28[1 x 8 x 9]m56[3 x 5 x 7]m84[7 x 8 x 9]

このｍ０１～ｍ８４を複数組み合わせて（ただし個々のゲームは０回ないし１回だけ行われる）、
　条件１　各プレーヤーは４回だけプレイする
　条件２　他のすべてのプレイヤーとちょうど１回ずつプレイする
の両条件を満たすゲームの組み合わせを考える。

仮に１２ゲーム必要なのだとしても（各プレイヤーが４回ずつ、１回のゲームで１／３の人しかプレイできないので　４×３＝１２より）、
{}_8{}_4 \mathrm{C}_1{}_2　＝　１１２，９９２，８９２，７６４，５７０
と百兆を超えるとても大きな数となり、手作業で考えるのはとうてい無理なので、コンピュータをつかう。
コンピュータを使っても総当たり法では組み合わせ爆発を起こすので、線形計画法ソルバを利用する。

ＧＬＰＫに与えるモデルファイルは次の通り。

game3.mod.txt
var m01	 binary;
var m02	 binary;
var m03	 binary;
var m04	 binary;
var m05	 binary;
var m06	 binary;
var m07	 binary;
var m08	 binary;
var m09	 binary;
var m10	 binary;
var m11	 binary;
var m12	 binary;
var m13	 binary;
var m14	 binary;
var m15	 binary;
var m16	 binary;
var m17	 binary;
var m18	 binary;
var m19	 binary;
var m20	 binary;
var m21	 binary;
var m22	 binary;
var m23	 binary;
var m24	 binary;
var m25	 binary;
var m26	 binary;
var m27	 binary;
var m28	 binary;
var m29	 binary;
var m30	 binary;
var m31	 binary;
var m32	 binary;
var m33	 binary;
var m34	 binary;
var m35	 binary;
var m36	 binary;
var m37	 binary;
var m38	 binary;
var m39	 binary;
var m40	 binary;
var m41	 binary;
var m42	 binary;
var m43	 binary;
var m44	 binary;
var m45	 binary;
var m46	 binary;
var m47	 binary;
var m48	 binary;
var m49	 binary;
var m50	 binary;
var m51	 binary;
var m52	 binary;
var m53	 binary;
var m54	 binary;
var m55	 binary;
var m56	 binary;
var m57	 binary;
var m58	 binary;
var m59	 binary;
var m60	 binary;
var m61	 binary;
var m62	 binary;
var m63	 binary;
var m64	 binary;
var m65	 binary;
var m66	 binary;
var m67	 binary;
var m68	 binary;
var m69	 binary;
var m70	 binary;
var m71	 binary;
var m72	 binary;
var m73	 binary;
var m74	 binary;
var m75	 binary;
var m76	 binary;
var m77	 binary;
var m78	 binary;
var m79	 binary;
var m80	 binary;
var m81	 binary;
var m82	 binary;
var m83	 binary;
var m84	 binary;

minimize z: m01 + m02 + m03 + m04 + m05 + m06 + m07 + m08 + m09 + m10 + m11 + m12 + m13 + m14 + m15 + m16 + m17 + m18 + m19 + m20 + m21 + m22 + m23 + m24 + m25 + m26 + m27 + m28 + m29 + m30 + m31 + m32 + m33 + m34 + m35 + m36 + m37 + m38 + m39 + m40 + m41 + m42 + m43 + m44 + m45 + m46 + m47 + m48 + m49 + m50 + m51 + m52 + m53 + m54 + m55 + m56 + m57 + m58 + m59 + m60 + m61 + m62 + m63 + m64 + m65 + m66 + m67 + m68 + m69 + m70 + m71 + m72 + m73 + m74 + m75 + m76 + m77 + m78 + m79 + m80 + m81 + m82 + m83 + m84 ;

s.t. st1: m01 + m02 + m03 + m04 + m05 + m06 + m07 + m08 + m09 + m10 + m11 + m12 + m13 + m14 + m15 + m16 + m17 + m18 + m19 + m20 + m21 + m22 + m23 + m24 + m25 + m26 + m27 + m28 = 4;
s.t. st2: m01 + m02 + m03 + m04 + m05 + m06 + m07 + m29 + m30 + m31 + m32 + m33 + m34 + m35 + m36 + m37 + m38 + m39 + m40 + m41 + m42 + m43 + m44 + m45 + m46 + m47 + m48 + m49 = 4;
s.t. st3: m01 + m08 + m09 + m10 + m11 + m12 + m13 + m29 + m30 + m31 + m32 + m33 + m34 + m50 + m51 + m52 + m53 + m54 + m55 + m56 + m57 + m58 + m59 + m60 + m61 + m62 + m63 + m64 = 4;
s.t. st4: m02 + m08 + m14 + m15 + m16 + m17 + m18 + m29 + m35 + m36 + m37 + m38 + m39 + m50 + m51 + m52 + m53 + m54 + m65 + m66 + m67 + m68 + m69 + m70 + m71 + m72 + m73 + m74 = 4;
s.t. st5: m03 + m09 + m14 + m19 + m20 + m21 + m22 + m30 + m35 + m40 + m41 + m42 + m43 + m50 + m55 + m56 + m57 + m58 + m65 + m66 + m67 + m68 + m75 + m76 + m77 + m78 + m79 + m80 = 4;
s.t. st6: m04 + m10 + m15 + m19 + m23 + m24 + m25 + m31 + m36 + m40 + m44 + m45 + m46 + m51 + m55 + m59 + m60 + m61 + m65 + m69 + m70 + m71 + m75 + m76 + m77 + m81 + m82 + m83 = 4;
s.t. st7: m05 + m11 + m16 + m20 + m23 + m26 + m27 + m32 + m37 + m41 + m44 + m47 + m48 + m52 + m56 + m59 + m62 + m63 + m66 + m69 + m72 + m73 + m75 + m78 + m79 + m81 + m82 + m84 = 4;
s.t. st8: m06 + m12 + m17 + m21 + m24 + m26 + m28 + m33 + m38 + m42 + m45 + m47 + m49 + m53 + m57 + m60 + m62 + m64 + m67 + m70 + m72 + m74 + m76 + m78 + m80 + m81 + m83 + m84 = 4;
s.t. st9: m07 + m13 + m18 + m22 + m25 + m27 + m28 + m34 + m39 + m43 + m46 + m48 + m49 + m54 + m58 + m61 + m63 + m64 + m68 + m71 + m73 + m74 + m77 + m79 + m80 + m82 + m83 + m84 = 4;


s.t. st12: m01 + m02 + m03 + m04 + m05 + m06 + m07 = 1;
s.t. st13: m01 + m08 + m09 + m10 + m11 + m12 + m13 = 1;
s.t. st14: m02 + m08 + m14 + m15 + m16 + m17 + m18 = 1;
s.t. st15: m03 + m09 + m14 + m19 + m20 + m21 + m22 = 1;
s.t. st16: m04 + m10 + m15 + m19 + m23 + m24 + m25 = 1;
s.t. st17: m05 + m11 + m16 + m20 + m23 + m26 + m27 = 1;
s.t. st18: m06 + m12 + m17 + m21 + m24 + m26 + m28 = 1;
s.t. st19: m07 + m13 + m18 + m22 + m25 + m27 + m28 = 1;
s.t. st23: m01 + m29 + m30 + m31 + m32 + m33 + m34 = 1;
s.t. st24: m02 + m29 + m35 + m36 + m37 + m38 + m39 = 1;
s.t. st25: m03 + m30 + m35 + m40 + m41 + m42 + m43 = 1;
s.t. st26: m04 + m31 + m36 + m40 + m44 + m45 + m46 = 1;
s.t. st27: m05 + m32 + m37 + m41 + m44 + m47 + m48 = 1;
s.t. st28: m06 + m33 + m38 + m42 + m45 + m47 + m49 = 1;
s.t. st29: m07 + m34 + m39 + m43 + m46 + m48 + m49 = 1;
s.t. st34: m08 + m29 + m50 + m51 + m52 + m53 + m54 = 1;
s.t. st35: m09 + m30 + m50 + m55 + m56 + m57 + m58 = 1;
s.t. st36: m10 + m31 + m51 + m55 + m59 + m60 + m61 = 1;
s.t. st37: m11 + m32 + m52 + m56 + m59 + m62 + m63 = 1;
s.t. st38: m12 + m33 + m53 + m57 + m60 + m62 + m64 = 1;
s.t. st39: m13 + m34 + m54 + m58 + m61 + m63 + m64 = 1;
s.t. st45: m14 + m35 + m50 + m65 + m66 + m67 + m68 = 1;
s.t. st46: m15 + m36 + m51 + m65 + m69 + m70 + m71 = 1;
s.t. st47: m16 + m37 + m52 + m66 + m69 + m72 + m73 = 1;
s.t. st48: m17 + m38 + m53 + m67 + m70 + m72 + m74 = 1;
s.t. st49: m18 + m39 + m54 + m68 + m71 + m73 + m74 = 1;
s.t. st56: m19 + m40 + m55 + m65 + m75 + m76 + m77 = 1;
s.t. st57: m20 + m41 + m56 + m66 + m75 + m78 + m79 = 1;
s.t. st58: m21 + m42 + m57 + m67 + m76 + m78 + m80 = 1;
s.t. st59: m22 + m43 + m58 + m68 + m77 + m79 + m80 = 1;
s.t. st67: m23 + m44 + m59 + m69 + m75 + m81 + m82 = 1;
s.t. st68: m24 + m45 + m60 + m70 + m76 + m81 + m83 = 1;
s.t. st69: m25 + m46 + m61 + m71 + m77 + m82 + m83 = 1;
s.t. st78: m26 + m47 + m62 + m72 + m78 + m81 + m84 = 1;
s.t. st79: m27 + m48 + m63 + m73 + m79 + m82 + m84 = 1;
s.t. st89: m28 + m49 + m64 + m74 + m80 + m83 + m84 = 1;
変数 m?? が、それぞれのゲームが行われる回数（０または１回）を表している。例えば変数 m03 は m03 のゲーム（１と２と５との対戦）が行われた回数を示す。

minimize z: で、目的関数（ダミーの式 ; m01 ～ m84 の合計 ; 条件１・２を満たすために合計何ゲーム必要なのか）を最小化させる解を求めることを指示している。
＃これは別に最大化でも何でもいいはず。条件１・２を考えると、目的関数の値は一種類しか取り得ない。
＃　　→そもそも、この行は無くてもかまわないようです。
＃しかしこの解き方のように、目的関数を最大化／最小化させる意図が無い問題は、じつは線形計画問題・整数計画問題にはあたらない（ただの連立方程式・不等式）のだろうか？
＃最適化を目指しているのではなくて、副産物的に手に入る解を拾い集めていくというやり方。

st1～9 で各人がちょうど４回だけプレイする（条件１）こと、st12～89 で同じ人とはちょうど１度だけプレイすること（条件２）を制約している。
st?? の 十の位・一の位の数字でおのおのプレイヤーを表している。例えば st38 は ３と８が対戦するゲーム（m12, m33, m53, m57, m60, m62, m64）の回数の合計がちょうど１回であるように制約してある。

次のように実行する。
glpsol -m game3.mod.txt -o game3.out.txt
実行結果 game3.out.txt の内容は次の通り。
Problem:    first
Rows:       46
Columns:    84 (84 integer, 84 binary)
Non-zeros:  588
Status:     INTEGER OPTIMAL
Objective:  z = 12 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 z                          12                             
     2 st1                         4             4             = 
     3 st2                         4             4             = 
     4 st3                         4             4             = 
     5 st4                         4             4             = 
     6 st5                         4             4             = 
     7 st6                         4             4             = 
     8 st7                         4             4             = 
     9 st8                         4             4             = 
    10 st9                         4             4             = 
    11 st12                        1             1             = 
    12 st13                        1             1             = 
    13 st14                        1             1             = 
    14 st15                        1             1             = 
    15 st16                        1             1             = 
    16 st17                        1             1             = 
    17 st18                        1             1             = 
    18 st19                        1             1             = 
    19 st23                        1             1             = 
    20 st24                        1             1             = 
    21 st25                        1             1             = 
    22 st26                        1             1             = 
    23 st27                        1             1             = 
    24 st28                        1             1             = 
    25 st29                        1             1             = 
    26 st34                        1             1             = 
    27 st35                        1             1             = 
    28 st36                        1             1             = 
    29 st37                        1             1             = 
    30 st38                        1             1             = 
    31 st39                        1             1             = 
    32 st45                        1             1             = 
    33 st46                        1             1             = 
    34 st47                        1             1             = 
    35 st48                        1             1             = 
    36 st49                        1             1             = 
    37 st56                        1             1             = 
    38 st57                        1             1             = 
    39 st58                        1             1             = 
    40 st59                        1             1             = 
    41 st67                        1             1             = 
    42 st68                        1             1             = 
    43 st69                        1             1             = 
    44 st78                        1             1             = 
    45 st79                        1             1             = 
    46 st89                        1             1             = 

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 m01          *              0             0             1 
     2 m02          *              0             0             1 
     3 m03          *              0             0             1 
     4 m04          *              1             0             1 
     5 m05          *              0             0             1 
     6 m06          *              0             0             1 
     7 m07          *              0             0             1 
     8 m08          *              0             0             1 
     9 m09          *              0             0             1 
    10 m10          *              0             0             1 
    11 m11          *              0             0             1 
    12 m12          *              1             0             1 
    13 m13          *              0             0             1 
    14 m14          *              1             0             1 
    15 m15          *              0             0             1 
    16 m16          *              0             0             1 
    17 m17          *              0             0             1 
    18 m18          *              0             0             1 
    19 m19          *              0             0             1 
    20 m20          *              0             0             1 
    21 m21          *              0             0             1 
    22 m22          *              0             0             1 
    23 m23          *              0             0             1 
    24 m24          *              0             0             1 
    25 m25          *              0             0             1 
    26 m26          *              0             0             1 
    27 m27          *              1             0             1 
    28 m28          *              0             0             1 
    29 m29          *              0             0             1 
    30 m30          *              0             0             1 
    31 m31          *              0             0             1 
    32 m32          *              0             0             1 
    33 m33          *              0             0             1 
    34 m34          *              1             0             1 
    35 m35          *              0             0             1 
    36 m36          *              0             0             1 
    37 m37          *              0             0             1 
    38 m38          *              1             0             1 
    39 m39          *              0             0             1 
    40 m40          *              0             0             1 
    41 m41          *              1             0             1 
    42 m42          *              0             0             1 
    43 m43          *              0             0             1 
    44 m44          *              0             0             1 
    45 m45          *              0             0             1 
    46 m46          *              0             0             1 
    47 m47          *              0             0             1 
    48 m48          *              0             0             1 
    49 m49          *              0             0             1 
    50 m50          *              0             0             1 
    51 m51          *              0             0             1 
    52 m52          *              1             0             1 
    53 m53          *              0             0             1 
    54 m54          *              0             0             1 
    55 m55          *              1             0             1 
    56 m56          *              0             0             1 
    57 m57          *              0             0             1 
    58 m58          *              0             0             1 
    59 m59          *              0             0             1 
    60 m60          *              0             0             1 
    61 m61          *              0             0             1 
    62 m62          *              0             0             1 
    63 m63          *              0             0             1 
    64 m64          *              0             0             1 
    65 m65          *              0             0             1 
    66 m66          *              0             0             1 
    67 m67          *              0             0             1 
    68 m68          *              0             0             1 
    69 m69          *              0             0             1 
    70 m70          *              0             0             1 
    71 m71          *              1             0             1 
    72 m72          *              0             0             1 
    73 m73          *              0             0             1 
    74 m74          *              0             0             1 
    75 m75          *              0             0             1 
    76 m76          *              0             0             1 
    77 m77          *              0             0             1 
    78 m78          *              0             0             1 
    79 m79          *              0             0             1 
    80 m80          *              1             0             1 
    81 m81          *              1             0             1 
    82 m82          *              0             0             1 
    83 m83          *              0             0             1 
    84 m84          *              0             0             1 

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output
これから、仮定の通り１２ゲーム必要であり、その組み合わせは、
m04, m12, m14, m27, m34, m38, m41, m52, m55, m71, m80, m81
であることがわかった（Activity が１となっている m?? の行を拾う）。
表１とつきあわせて対戦表にすると、
[ 1 x 2 x 6 ] [ 1 x 3 x 8 ] [ 1 x 4 x 5 ] [ 1 x 7 x 9 ] [ 2 x 3 x 9 ] [ 2 x 4 x 8 ]
[ 2 x 5 x 7 ] [ 3 x 4 x 7 ] [ 3 x 5 x 6 ] [ 4 x 6 x 9 ] [ 5 x 8 x 9 ] [ 6 x 7 x 8 ]
となる。
組み合わせのパターンは複数あると思われるので、１度出たパターンは２度と現れないようにしてもう１度問題を解いてゆく。
具体的には、モデルファイルの末尾に
s.t. pm1: m04 + m12 + m14 + m27 + m34 + m38 + m41 + m52 + m55 + m71 + m80 + m81 <= 11;
を追記して、解く。

この、得られた解が現れないようにする制約式を、追記をしてはまた解くということを、解が得られなくなるまで繰り返す。
具体的には、 sol.pl を実行して、エラーが出るまで待つ。
もし、最後までエラーを出さないようなら、for ループの上限の数字を大きくして再度実行する。
そうしたところ、８４０個の解が得られた後、新たな解を返さなくなった。

最終的に得られたモデルファイルは、次の通り。こちら→　joined.mod.txt
「s.t. pm840:～」まで生成されているのがわかる（最終行）。

問題の「ゲームの個数（＝試合数）は何通りあるか」には少々文意がつかみかねるが、
「８４０通り」と答えた。

出来上がった joined.mod.txt から「s.t. pm???:～」行を拾い集めて、これだと各対戦が m?? 形式になっているので、
それを対戦表の形式に変換する（じっさいには中間ファイル prev_match_pattern.txt から make_match_table.pl を使って生成する）。
得られた対戦表は、こちら→　対戦表.txt

ツール類

Perl で書いた各種自動化ツールはこんな感じです。
Windows のコマンドライン上で動かしました。

sol.pl
use strict;

unlink('prev_match_pattern.txt');

system('glpsol -m game3.mod.txt -o game3.out.txt');

for(my $i = 1; $i <= 1000; $i++){
	print"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
	print "■■■■■ $i ■■■■■\n";

	system('type game3.out.txt | perl pattern.pl >> prev_match_pattern.txt');
	system('type prev_match_pattern.txt | perl make_st_prev_match_pattern.pl > st_prev_match.txt');

	system('copy game3.mod.txt + st_prev_match.txt joined.mod.txt');

	system('glpsol -m joined.mod.txt -o game3.out.txt');
}

pattern.pl
use strict;

my @matches;
foreach my $line (<>){
	chomp($line);

	if($line =~ /(m\d\d)\s+\*\s+(\d)/){
		push(@matches, $1) if($2 == 1);
	}
}

print join(',', @matches). "\n";

make_st_prev_match_pattern.pl
use strict;

my $i = 1;
foreach my $line (<>){
	chomp $line;
	my @mts = split(/,/, $line);
	print "s.t. pm$i: ". join(' + ', @mts). " <= 11;\n";

	$i++;
}

制約式を生成するスクリプト st.pl　（game3.mod.txt を用意するときに使う）
use strict;
use warnings;
use Math::Combinatorics;

my @matches;
push @matches, '0';
open(LIST, '9c3.txt');
foreach my $line(<LIST>){
	chomp $line;
	push @matches, $line;
}
close(LIST);


foreach my $player (1..9){
	my @joined_match;
	print "s.t. st$player: ";
	foreach my $match (1..84){
		if($matches[$match] =~ /$player/){
			push @joined_match, sprintf('m%02d', $match);
		}
	}
	
	print join(' + ', @joined_match). " = 4;\n";
}

print "\n";

my @combine = combine(2, 1..9);
@combine = sort {$a->[0] <=> $b->[0]} @combine;
foreach my $a_comb (@combine) {
	my @hit_match;
    my($p1, $p2) = @$a_comb;
    ($p1, $p2) = sort ($p1, $p2);
	print "s.t. st${p1}${p2}: ";
	foreach my $match (1..84){
		if($matches[$match] =~ /$p1/ && $matches[$match] =~ /$p2/){
			push @hit_match, sprintf('m%02d', $match);
		}
	}
	
	print join(' + ', @hit_match). " = 1;\n";
}

組み合わせ（{}_9 \mathrm{C}_3）データファイル 9c3.txt
(1,2,3)
(1,2,4)
(1,2,5)
(1,2,6)
(1,2,7)
(1,2,8)
(1,2,9)
(1,3,4)
(1,3,5)
(1,3,6)
(1,3,7)
(1,3,8)
(1,3,9)
(1,4,5)
(1,4,6)
(1,4,7)
(1,4,8)
(1,4,9)
(1,5,6)
(1,5,7)
(1,5,8)
(1,5,9)
(1,6,7)
(1,6,8)
(1,6,9)
(1,7,8)
(1,7,9)
(1,8,9)
(2,3,4)
(2,3,5)
(2,3,6)
(2,3,7)
(2,3,8)
(2,3,9)
(2,4,5)
(2,4,6)
(2,4,7)
(2,4,8)
(2,4,9)
(2,5,6)
(2,5,7)
(2,5,8)
(2,5,9)
(2,6,7)
(2,6,8)
(2,6,9)
(2,7,8)
(2,7,9)
(2,8,9)
(3,4,5)
(3,4,6)
(3,4,7)
(3,4,8)
(3,4,9)
(3,5,6)
(3,5,7)
(3,5,8)
(3,5,9)
(3,6,7)
(3,6,8)
(3,6,9)
(3,7,8)
(3,7,9)
(3,8,9)
(4,5,6)
(4,5,7)
(4,5,8)
(4,5,9)
(4,6,7)
(4,6,8)
(4,6,9)
(4,7,8)
(4,7,9)
(4,8,9)
(5,6,7)
(5,6,8)
(5,6,9)
(5,7,8)
(5,7,9)
(5,8,9)
(6,7,8)
(6,7,9)
(6,8,9)
(7,8,9)

対戦表出力スクリプト make_match_table.pl
use strict;

my @a9c3;
push(@a9c3, '0');

open(F9C3, '9c3.txt');
foreach my $line_9c3 (<F9C3>){
	chomp $line_9c3;
	$line_9c3 =~ /(\d),(\d),(\d)/;
	push(@a9c3, [$1, $2, $3] );
}

close(F9C3);



my $i = 1;
open(PMP, 'prev_match_pattern.txt');

foreach my $line_pmp (<PMP>){
	chomp $line_pmp;
	print "■■■ 対戦表\ No. $i ■■■  ($line_pmp)\n";
	my @ms = split(/,/, $line_pmp);
	my $j = 0;
	foreach my $a_match (@ms){
		$j++;
		$a_match =~ /m(\d\d)/;
		my $m = int($1);
		print "[ ". $a9c3[$m]->[0]. ' x '. $a9c3[$m]->[1]. ' x '. $a9c3[$m]->[2]. " ] ";
		print "\n" if ($j % 6 == 0);
	}
	
	print "\n";
	$i++;
}


close(PMP);

参考にしたもの

不要な解（孤立ループ）を取り除いてはまたソルバを動かすのを繰り返す、というやり方からヒントを得ました。


目的関数の定義、minimize 行は必須では無いことを知りました。