blog.monophile.net

コンピュータのこととかのメモ。

Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、 情報科学芸術大学院大学[IAMAS] においてメディア表現を専攻し修了。 現在は digitiminimi Inc. において、インフラエンジニアとして生計をたててている。

work

各種システム構築と管理を承ります。

Cloud PlatformOpenstack, GCP, AWS, Azure, ...
Openstackkeystone, glance, cinder, swift, neutron, nova, ...
VirtualizationQEMU+KVM, LXD/LXC, Docker, ...
OSDebian GNU/Linux, Ubuntu, CentOS, ...
NetworksIPSec, L2TP, VXLAN, WirelessAP, ...
WebAppsWordPress, GitLab, Redmine, ...
Configuration ManagementAnsible, Terraform, ...
MonitoringNagios, Munin, ...

posts

glpsolで線形計画問題を解く

概要

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

線形計画問題

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

\[ A \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^{m}, \mathbf{c} \in \mathbb{R}^{n} \\ \max_{\mathbf{x} \in \mathbb{R}^n}{\mathbf{c}^T \mathbf{x}} \\ \text{s.t.}\ \left\{ A\mathbf{x} \geq \mathbf{b}, x_i \geq 0 \ for \ \forall i \in \{1, \ldots, n\} \right\} \]

install glpk

Ubuntuの場合は↓。

$ sudo apt-get install glpk

コーディング

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;

実行

ここではモデルファイルを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条件まで表示される。