blog.monophile.net

コンピュータに関するメモ。

著者

山本一彰(Takaaki Yamamoto)

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

投稿

GLPK の GLPSOL を使って線形計画問題を解く

概要

自分で線形計画問題のソルバを実装していて、検算したくなったので、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 の場合は↓。

モデルファイル 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 に保存する。

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

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

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条件なども出力されていた。