glpsolで線形計画問題を解く

abstract

glpsolというコマンドを使って線形計画問題を解きます。

線形計画問題の標準形

今回は、線計画問題を以下のように定義します。

インストール

自分が使っているのはUbuntuなのでaptを使います。

$ sudo apt-get install glpk

これでglpsolが使えるようになります。

コーディング

glpsolでは、問題の定義のためのモデルファイルと、問題を決定する行列のデータを記入するデータファイルが分離されます。

model.m

特には説明いたしません。ソースコード自体が結構わかりやすい文法で書かれていると思います。

set M;
set N;
var X{N} >=0;
param Obj{N};
param A{M,N};
param B{M};

maximize OBJ:
  sum{n in N} Obj[n] * X [n];

s.t.  CONSTRAINT{m in M}:
  sum{n in N} A[m,n] * X[n] >= B[m];
end;

data.d

このファイルで制約式と目的関数の具体的なデータを記述します。

set M := m0 m1 m2;
set N := n0 n1;

param Obj :=
n0    18
n1    11;

param A:
      n0 n1 :=
m0    1  1
m1    2  0
m2    0  1;

param B:=
m0    40
m1    50
m2    25;

end;

execution

ここまでで準備ができたので、実行してみます。

ここではモデルファイルをmodel.m、データファイルをdata.dとして、実行結果をout.txtに保存します。

$ glpsol -m model.m -d data.d -o out.txt

ここで、モデルファイルとデータファイルに不正合がある場合はその旨がコンソールに表示されます。 正常に実行できた場合は以下のように表示されます。

GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
 -m model.m -d data.d -o out.txt
Reading model section from model.m...
14 lines were read
Reading data section from data.d...
data.d:19: warning: final NL missing before end of file
19 lines were read
Generating OBJ...
Generating CONSTRAINT...
Model has been successfully generated
GLPK Simplex Optimizer, v4.45
4 rows, 2 columns, 6 non-zeros
Preprocessing...
1 row, 2 columns, 2 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 1
      0: obj =   4.400000000e+02  infeas =  1.500e+01 (0)
*     1: obj =   2.750000000e+02  infeas =  0.000e+00 (0)
*     3: obj =   6.150000000e+02  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (138567 bytes)
Writing basic solution to `out.txt'...

out.txt

Problem:    max
Rows:       4
Columns:    2
Non-zeros:  6
Status:     OPTIMAL
Objective:  OBJ = 615 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 OBJ          B            615                             
     2 CONSTRAINT[m0]
                    NU            40                          40            11
     3 CONSTRAINT[m1]
                    NU            50                          50           3.5
     4 CONSTRAINT[m2]
                    B             15                          25

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 X[n0]        B             25             0               
     2 X[n1]        B             15             0               

Karush-Kuhn-Tucker optimality 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

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

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

End of output

最適値は615、最適解は(25,15)で、KKT条件まで調べてくれています。