blog.monophile.net

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

山本 一彰 | Takaaki Yamamoto

東京工業大学において計算機科学と応用数学を学び、 情報科学芸術大学院大学[IAMAS]においてメディア表現を専攻し修了。 2015年にコンビネータ論理を基に計算完備な計算手法 "論理珠算"を開発し、 それを含む体系である"算道"を構成した。 その成果により、 第19回 文化庁メディア芸術祭 アート部門 新人賞 (文部科学大臣賞) を2016年に受賞。 現在はインフラエンジニアとして生計をたててている。

技術

各種システムの設計/構築/運用を承ります。

Configuration Management Ansible, Terraform, cloud-init
Cloud Platform AWS, Azure, GCP, Openstack
Openstack Keystone, Glance, Cinder(Ceph), Neutron(VLAN), Nova(QEMU), Horizon
Virtualization QEMU+KVM, LXD/LXC, Docker
OS Ubuntu, Debian GNU/Linux, CentOS, ...
Storage Ceph, GlusterFS, ZFS, btrfs, ...
Networks Tunnel(IPSec, L2TP, VXLAN, GRE), WirelessAP, ...
DB MySQL, MariaDB(Galera Cluster), MongoDB
Mail postfix, dovecot
WebApps WordPress, GitLab, MatterMost, Redmine, RainLoop, ...
Monitoring Nagios, Munin
Misc certbot, dnsmasq, ...

技術(習得中)

Orchestration Kubernetes
Openstack swift, manila, trove
OS CoreOS(Container Linux), Vyatta(VyOS), ...
Networks IPv6, BGP(quagga, calico), flannel, fan, ...
DB/KVS Redis, etcd
Monitoring Prometheus, Zabbix
DNS CoreDNS, PowerDNS
Misc MAAS, Blockchain

投稿

glpsolで線形計画問題を解く

概要

自分で線形計画問題のソルバを実装していて、検算したくなったので、glpkを使ってみた。 glpkに含まれる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} \leq \mathbf{b}, x_i \geq 0 \ for \ \forall i \in \{1, \ldots, n\} \right\} \]

glpsolをインストールする

Ubuntu16.04の場合は↓。

$ sudo apt-get install glpk-utils

モデルファイル model.m

モデルファイル model.m に上記で定義した線形計画問題を記述する。

set M;
set N;
var X{N} >=0;
param A{M,N};
param b{M};
param c{N};

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

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

データファイル data.d

データファイル data.d に具体的な制約式と目的関数を指定するために、 行列Aとベクトルbベクトルcのデータを記述する。

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

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

param b :=
m0    40
m1    50
m2    25;

param c :=
n0    18
n1    11;

end;

glpsolを実行

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

$ glpsol -m model.m -d data.d -o out.txt
GLPSOL: GLPK LP/MIP Solver, v4.57
Parameter(s) specified in the command line:
 -m model.m -d data.d -o out.txt
Reading model section from model.m...
13 lines were read
Reading data section from data.d...
19 lines were read
Generating OBJ...
Generating CONSTRAINT...
Model has been successfully generated
GLPK Simplex Optimizer, v4.57
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 is 1
*     0: obj =  -0.000000000e+00 inf =   0.000e+00 (2)
*     2: obj =   6.150000000e+02 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (126356 bytes)
Writing basic solution to 'out.txt'...

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

実際の計算結果は↓のように出力される。

$ cat out.txt
Problem:    model
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条件なども出力されていた。