GLPKプログラミングの基礎(1)

<-目次
##はじめに
京都駅の大階段を駆け上るレースが毎年行われています。
第21回 JR京都駅ビル 大階段駈け上がり大会
それに参加するためのチームを作ってみます。1チーム4人ですのでまず4人ずつにチーム分けします。

参加者は次の通りです。

氏名	性別	年齢	記録(秒)
Aさん	男	30	40
Bさん	男	18	25
Cさん	女	25	35
Dさん	女	18	33
Eさん	男	48	45
Fさん	男	30	28
Gさん	女	45	48
Hさん	女	20	32

##プログラム
まず次表のようなバイナリ変数を用意します。空欄になっているところに、該当する場合には1、しない場合には0を入れることでチームを分けます。

例えばAさんがチーム1に属すなら左上が1、その下に0が入ります。全員どちらかのチームに属しますので、縦方向の合計が必ず1になります。また各チーム4人ですので横方向の合計が必ず4になります。
以上の条件をGLPKのMathProgで書くと

team1.mod

# version 0.1
set N := {"Aさん", "Bさん", "Cさん", "Dさん", "Eさん", "Fさん", "Gさん", "Hさん"};
set T := {"チーム1", "チーム2"};
var w{N, T} binary;
s.t. belong_one_team{n in N}: sum{t in T}w[n,t]==1;
s.t. team_members{t in T}: sum{n in N}w[n,t]==4;
solve;
display w;

のようになります。
solveでそこまでの条件で解を求め、displayで変数の内容を表示します。

チームを作る上で、女性と45歳以上が1名含まれるルールがありそれを追加します。
いくつかの属性を読み込む必要がありますので、データ部分を分離し、最初の方で読み込むようにしています。
それと結果を見やすくなるように出力文を追加していますが、基本的にはteam1.modに制約条件(s.t.文)を2つ追加しただけです。

team2.mod

# version 0.2
set T; # チーム名を読み込む
set N; # 氏名を読み込む
param s{N} symbolic; # 性別を読み込む
param a{N}; # 年齢を読み込む
param r{N}; # 記録を読み込む
var w{N, T} binary;
s.t. belong_one_team{n in N}: sum{t in T}w[n,t]==1;
s.t. team_members{t in T}: sum{n in N}w[n,t]==4;
s.t. gte45{t in T}: sum{n in N: a[n]>=45}w[n,t]>=1;
s.t. women{t in T}: sum{n in N: s[n]=="女"}w[n,t]>=1;
solve;
for{t in T}{
  printf "%s\n", t;
  printf{n in N: w[n,t]==1} "%s  %s  %d\n", n, s[n], a[n];
}

プログラム部分とデータ部分を分けてあります。慣れないうちはプログラム部分の後に次のデータを追加したファイルを作成して実行してみてください。

data;
set T := "チーム1" "チーム2";
param : N : s a r :=
"Aさん"	"男"	30	40
"Bさん"	"男"	18	25
"Cさん"	"女"	25	35
"Dさん"	"女"	18	33
"Eさん"	"男"	48	45
"Fさん"	"男"	30	28
"Gさん"	"女"	45	48
"Hさん"	"女"	20	32
;

ともかくそれっぽくチーム分けできていますが、女性で45歳以上の人を二重に数えてしまう可能性がありますので考え直して見ます。
公式には、
第1走者 : 45歳以上の方
第2走者 : 18歳以上の女性
第3・4走者 : 18歳以上の方
となっていますので、出走順に分けてみます。変数を次のように変更します。

縦方向の合計は1のままですが、横方向の合計は1になります。
それから出走順1は45歳以上であること、出走順2は女性である制約条件が追加されます。

team3.mod

# version 0.3
set T; # チーム名を読み込む
set N; # 氏名を読み込む
set O := 1..4; # 出走順
param s{N} symbolic; # 性別を読み込む
param a{N}; # 年齢を読み込む
param r{N}; # 記録を読み込む
var w{N, O, T} binary;
s.t. belong_one_team{n in N}: sum{t in T, o in O}w[n,o,t]==1;
s.t. team_members{t in T, o in O}: sum{n in N}w[n,o,t]==1;
s.t. gte45{t in T}: sum{n in N: a[n]>=45}w[n,1,t]==1; # 第一走者
s.t. women{t in T}: sum{n in N: s[n]=="女"}w[n,2,t]==1; # 第二走者
# minimize record: sum{t in {"チーム1"}, o in O, n in N}w[n,o,t]*r[n];
solve;
for{t in T}{
  printf "%s\n", t;
  printf{o in O, n in N : w[n,o,t]==1} "%d %s  %s  %d\n", o, n, s[n], a[n];
}

おまけですが、チーム1を最速のチームにしてみます。
上のプログラムでは
# minimize 〜とコメントにしていますが、先頭の#を消して実行するとそのようなチーム分けができます。