はじめに
整数計画ソルバーの基本的な使い方を紹介します。
OS別のインストール方法などは
GLPKによる勤務シフト表の作成1
からたどってください。
例1
以下に示す重量のジャガイモがあります。1kg入り(1kg以上)を10袋作りたいのですが、どのように詰めれば良いのでしょうか？
46g 17個
47g 20個
48g 22個
49g 16個
50g 21個
51g 22個
52g 25個
53g 21個
54g 16個
55g 21個
GLPKで動くプログラムを書いてみました。今回はモデルとデータを分けてあります。別々のファイルにして
glpsol -m packing1.mod -d data1.txt
で実行できます。またそのままつなげて1つのファイルにしても構いません。
set Package; # 袋の番号
set Weight; # 重量
param n{Weight}; # 重量ごとの個数
var assign{Package, Weight} integer, >=0; # 詰める個数
s.t. limit{w in Weight}: sum{p in Package}assign[p,w]<=n[w]; # それぞの重量の個数の上限
s.t. packing{p in Package}: sum{w in Weight}w*assign[p, w]>=1000; # 袋の中身が1000g以上
solve;
# 出力
printf "Package ";
printf{w in Weight}"%4d", w;
printf "\n";
for{p in Package}{
printf " %3d ", p;
printf{w in Weight}"%4d", assign[p, w];
printf "\n";
}
printf "Sum ";
printf{w in Weight}"%4d", sum{p in Package}assign[p, w];
printf "\n";
data;
# 袋の番号
set Package := 1 2 3 4 5 6 7 8 9 10;
# 1個あたりの重量と個数
param : Weight : n :=
46 17
47 20
48 22
49 16
50 21
51 22
52 25
53 21
54 16
55 21
;
しばらくすると、答えが出力されます。私の環境では以下のようになりました。条件を満たす答えが多種類ありますので、同じ結果になるとは限りません。
Package 46 47 48 49 50 51 52 53 54 55
1 0 0 0 0 0 0 0 0 0 19
2 0 0 0 0 0 0 1 0 16 2
3 0 0 0 0 0 0 0 19 0 0
4 0 0 1 0 0 1 17 1 0 0
5 0 0 1 0 0 13 6 0 0 0
6 0 13 7 0 0 0 0 1 0 0
7 0 0 0 3 14 3 0 0 0 0
8 2 0 13 6 0 0 0 0 0 0
9 0 0 0 7 7 5 1 0 0 0
10 15 7 0 0 0 0 0 0 0 0
Sum 17 20 22 16 21 22 25 21 16 21
1kg以上になる条件にしましたので、全部を詰めた太っ腹な結果になりました。（多分たまたま）
solve;より上に
minimize tatal_packing_weight: sum{p in Package, w in Weight}w*assign[p, w];
この1行を追加すると袋詰めする総重量が最小化されます。
+ 87727: mip = 1.011300000e+04 >= 1.000000000e+04 1.1% (43194; 4913)
+ 94668: mip = 1.011300000e+04 >= 1.000000000e+04 1.1% (46780; 5378)
+100669: mip = 1.011300000e+04 >= 1.000000000e+04 1.1% (49826; 5818)
+106053: mip = 1.011300000e+04 >= 1.000000000e+04 1.1% (52275; 6280)
+111379: mip = 1.011300000e+04 >= 1.000000000e+04 1.1% (55292; 6672)
+116711: mip = 1.011300000e+04 >= 1.000000000e+04 1.1% (58408; 7048)
こんなメッセージが延々と出てきますが、私の非力なパソコンではしばらく待っても答えを返しくれませんでした。
mip =の後に、2つの数値が表示されている時には、最適解は見つかっていないけれど、条件を満たしてい許容解は見つかってます。
待てない人は、コマンドに
--tmlim 60
を追加すると、指定時間後に制約条件を満たした答が出力されます。(この場合は60秒)
また、一番重い袋の重量を最小化する方法もあります。
var max_package_weight integer;
s.t. max_paking_weigth{p in Package}: sum{w in Weight}w*assign[p, w]<=max_package_weight;
minimize pack_weight: max_package_weight;
max_package_weightに一番重い袋の重量が入ります。
「整数計画ソルバーの使い方2」に続く予定