GLPKのテスト

glpk の使用

• glpkとはなにか
  • GNU Linear Programming Kit の略
  • 線形計画問題を解くことができる
  • たとえば https://qiita.com/youwht/items/9098d560f28d16aa5567 のマクドナルド問題

	カロリー	栄養１	栄養２	栄養３
てりやき	20	25	10	15
ポテト	12	11	10	18
コーラ	15	13	16	25
必要栄養量	★ここを最小にしたい	最低300	最低200	最低100

• 一番下の行の各栄養素量を満たすために、いくつずつ摂取すればいいかを知りたい

  • ただしカロリーは最小にしたい

• これを計算するために GLPKを使う

• インストール

  • GLPK をダウンロード, configure, make install / or brew install glpk

• GLPK を使うための mod ファイルを作る

  • これは MathProg という独自のプログラムを使ってソルバーを定義できる
  • 上記の表のマクドナルド問題を解くためには

var teriyaki , integer,  >= 0;
var potato , integer,  >= 0;
var cola , integer,  >= 0;

minimize z: 20*teriyaki + 12*potato + 15*cola;
s.t. st1: 25*teriyaki + 11*potato + 13*cola>=300;
s.t. st2: 10*teriyaki + 10*potato + 16*cola>=200;
s.t. st3: 15*teriyaki + 18*potato + 25*cola>=100;

solve;

printf "teriyaki %d, potato %d, cola %d\n", teriyaki, potato, cola;

end;

• このような modファイルを作り、 GLPKに食わせる
• glpsol -m test.mod

GLPSOL--GLPK LP/MIP Solver 5.0
Parameter(s) specified in the command line:
 -m test.mod
Reading model section from test.mod...
14 lines were read
Generating z...
Generating st1...
Generating st2...
Generating st3...
Model has been successfully generated
GLPK Integer Optimizer 5.0
4 rows, 3 columns, 12 non-zeros
3 integer variables, none of which are binary
Preprocessing...
3 rows, 3 columns, 9 non-zeros
3 integer variables, none of which are binary
Scaling...
 A: min|aij| =  1.000e+01  max|aij| =  2.500e+01  ratio =  2.500e+00
GM: min|aij| =  7.474e-01  max|aij| =  1.338e+00  ratio =  1.790e+00
EQ: min|aij| =  5.586e-01  max|aij| =  1.000e+00  ratio =  1.790e+00
2N: min|aij| =  3.438e-01  max|aij| =  1.000e+00  ratio =  2.909e+00
Constructing initial basis...
Size of triangular part is 3
Solving LP relaxation...
GLPK Simplex Optimizer 5.0
3 rows, 3 columns, 9 non-zeros
      0: obj =   0.000000000e+00 inf =   2.500e+01 (3)
      3: obj =   2.740740741e+02 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+     3: mip =     not found yet >=              -inf        (1; 0)
Solution found by heuristic: 277
+     6: mip =   2.770000000e+02 >=     tree is empty   0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (125022 bytes)
teriyaki 8, potato 1, cola 7
Model has been successfully processed

• ここが重要

teriyaki 8, potato 1, cola 7