整数計画法を用いた最適化計算

無収水対策の最適案は 、整数計画法を用いて、 第３章で述べた制約条件式の下で 、目 的関数である無収水量NRWjを最小化する非負整数Xijを求めることで得られる 。整数計画 法は、コンピューターを用いて 定式化された問題を解くための「ソルバー」と呼ばれる 計算ソフトを利用することが可能である。ソルバー には様々な種類のものがあり、大規 模で複雑な問題を解くために有料で販売されているソルバー（商用ソルバー）と、主に 学術研究用に無償で公開されている非商用ソルバーがある。本研究では、 非商用ソルバ ーのうち最も高速なものの1つであるSCIP（宮代隆平. 2012）を用いて計算を行った。SCIP は、ドイツのZuse Institute Berlinが開発した非商用ソルバーであり、ソースコードも含め て全て公開されている。インターフェースがシンプルで使いやすく、計算速度が速いと いう特徴を持つ。ウェブサイト http://scip.zib.de/ から無償でダウンロードすることが可 能である。本研究では、Windows向けバージョン3.2.0を用いた。

SCIPを用いた計算を行うためには、まず整数計画問題を記述したLPファイルと呼ばれ

る拡張子が「.lp」のテキストファイルを作成する。LPファイルは、①目的関数セクショ ン、②制約式セクション、③上下限セクション、④変数型セクション、⑤end宣言に分か れる。①目的関数セクションには、最大化問題か最小化問題かを示す予約語と、線形式 の目的関数を記述する。本研究の場合は、無収水量NRWjの最小化問題であるため、予約 語は「minimize」となる。目的関数は ３.４に示したとおりである。②制約式セクション に は 、 等 号 や 不 等 号 を 含 む 線 形 式 で 作 成 し た 制 約 条 件 を 記 述 す る 。 制 約 条 件 式 は 、 ３. ５に示したとおりである。③上下限セクションは、それぞれの変数が非負変数なのか、

負の値も取り得る変数（自由変数）なのかを指定するセクションであるが、何も指定し ない場合は自動的に非負変数と定義される。本研究の場合は、変数が無収水対策の実施 数量であり、非負変数であることは明らかであることから、上下限セクションは省略し た。④変数型セクションは、変数が整数変数なのか、0か1しか取らないバイナリ変数な のかを指定するセクションであり、 整数変数の場合は予約語「general」の後に該当する 変数を並べて記述する。本研究の変数は整数変数であるため、本セクションで変数型の 指定を行った。⑤end宣言は、LPファイルの最後の行に予約語「end」を置くことによっ

99

て、LPファイルの完結を示す部分である。

LPファイルの作成にあたっては、変数以外の係数や定数項は全て予め計算して数値と して記述する必要がある。そのため、エクセルのスプレッドシートを用いて、 第３章で 示した目的関数式や制約条件式に 第１章で示したパラメーター入力値を入れ、目的関数 と各年の制約条件式の係数や定数項を計算した。

以 上 の 手 順 で 作 成 し たLPフ ァ イ ル をSCIPの 実 行 フ ァ イ ル と 同 じ フ ォ ル ダ に 格 納 し 、

SCIPを起動させ、コマンド入力画面で「read ○○.lp」と入力すると、LPファイルがSCIP

に読み込まれる。コマンド「optimize」を入力すると最適化計算が開始され、最適解が 得 られる。コマンド「write solution ○○.sol」と入 力することにより、 最適解となる変数 の値と、その時に目的関数が取る値を示したテキストファイルが、「.sol」という拡張子 で作成される。

本研究で作 成したLPファ イルの一例 を以下 に示す 。 「x(i,j)」 と 書かれ て いるのが変 数Xijである。施設条件や予算制約を変えると、LPファイルに記述された式の係数や定数 項が変化することになる。

minimize

- 249.63 x(1,1) - 256.95 x(1,2) - 265.89 x(1,3) - 278.07 x(1,4) - 300 x(1,5) - 249.63 x(2,1) - 256.95 x(2,2) - 265.89 x(2,3) - 278.07 x(2,4) - 300 x(2,5) - 600 x(3,1) - 600 x(3,2) - 600 x(3,3) - 600 x(3,4) - 600 x(3,5) - 6.626 x(4,1) - 5.872 x(4,2) - 4.865 x(4,3) - 3.576 x(4,4) - 1.972 x(4,5) - 42048 x(5,1) - 42048 x(5,2) - 42048 x(5,3) - 42048 x(5,4) - 42048 x(5,5) - 132 x(6,1) - 124 x(6,2) - 109 x(6,3) - 84 x(6,4) - 48 x(6,5) - 11212.8 x(7,1) - 11212.8 x(7,2) - 11212.8 x(7,3) - 11212.8 x(7,4) - 11212.8 x(7,5)

subject to

m11: x(1,1) <= 30000

m12: x(1,1) + x(1,2) <= 32952

m13: 0.9269 x(1,1) + x(1,2) + x(1,3) - 0.0731 x(2,1) <= 35843

m14: 0.8863 x(1,1) + 0.9269 x(1,2) + x(1,3) + x(1,4) - 0.1137 x(2,1) - 0.0731 x(2,2) <= 38822 m15: 0.8565 x(1,1) + 0.8863 x(1,2) + 0.9269 x(1,3) + x(1,4) + x(1,5) - 0.1435 x(2,1) - 0.1137 x(2,2) - 0.0731 x(2,3) <= 42046

m21: x(2,1) <= 50000

m22: x(2,1) + x(2,2) <= 50000

m23: x(2,1) + x(2,2) + x(2,3) <= 50000

m24: x(2,1) + x(2,2) + x(2,3) + x(2,4) <= 50000

① 目的関数セクション

② 制約式セクション

100

m25: x(2,1) + x(2,2) + x(2,3) + x(2,4) + x(2,5) <= 50000 i1: x(3,1) <= 10000

i2: x(3,1) + x(3,2) <= 10500

i3: x(3,1) + x(3,2) + x(3,3) <= 11000

i4: x(3,1) + x(3,2) + x(3,3) + x(3,4) <= 11500

i5: x(3,1) + x(3,2) + x(3,3) + x(3,4) + x(3,5) <= 12000 d11: x(5,1) <= 221

d12: 0.0000189348 x(4,1) + x(5,1) + x(5,2) <= 315.674

d13: 0.0000433014 x(4,1) + 0.0000243844 x(4,2) + x(5,1) + x(5,2) + x(5,3) <= 437.596 d14: 0.0000739407 x(4,1) + 0.0000551393 x(4,2) + 0.0000307727 x(4,3) + x(5,1) + x(5,2) + x(5,3) + x(5,4) <= 591.4595

d15: 0.0001116776 x(4,1) + 0.0000931762 x(4,2) + 0.0000689252 x(4,3) + 0.0000381703 x(4,4) + x(5,1) + x(5,2) + x(5,3) + x(5,4) + x(5,5) <= 782.311

d21: x(4,1) <= 100000 d22: x(4,2) <= 100000 d23: x(4,3) <= 100000 d24: x(4,4) <= 100000 d25: x(4,5) <= 100000 s11: x(7,1) <= 210

s12: 0.000975301 x(6,1) + x(7,1) + x(7,2) <= 405.06022

s13: 0.002496665 x(6,1) + 0.001526698 x(6,2) + x(7,1) + x(7,2) + x(7,3) <= 710.39974 s14: 0.00470745 x(6,1) + 0.003772157 x(6,2) + 0.002250793 x(6,3) + x(7,1) + x(7,2) + x(7,3) + x(7,4) <= 1160.55838

s15: 0.00774725 x(6,1) + 0.0064772 x(6,2) + 0.005415289 x(6,3) + 0.00316983 x(6,4) + x(7,1) + x(7,2) + x(7,3) + x(7,4) + x(7,5) <= 1794.5244

s21: x(6,1) <= 10000 s22: x(6,2) <= 10000 s23: x(6,3) <= 10000 s24: x(6,4) <= 10000 s25: x(6,5) <= 10000

c1: 1500 x(1,1) + 6300 x(2,1) + 6300 x(3,1) + 6000 x(4,1) + 5000 x(5,1) + 7000 x(6,1) + 2000 x(7,1) <= 270000000

c2: 1500 x(1,2) + 6300 x(2,2) + 6300 x(3,2) + 6000 x(4,2) + 5000 x(5,2) + 7000 x(6,2) + 2000 x(7,2) <= 270000000

c3: 1500 x(1,3) + 6300 x(2,3) + 6300 x(3,3) + 6000 x(4,3) + 5000 x(5,3) + 7000 x(6,3) + 2000 x(7,3) <= 270000000

c4: 1500 x(1,4) + 6300 x(2,4) + 6300 x(3,4) + 6000 x(4,4) + 5000 x(5,4) + 7000 x(6,4) + 2000 x(7,4) <= 270000000

c5: 1500 x(1,5) + 6300 x(2,5) + 6300 x(3,5) + 6000 x(4,5) + 5000 x(5,5) + 7000 x(6,5) + 2000

c1～c5は予算制約に関する 制約条件式 を示す

101

x(7,5) <= 270000000 general

x(1,1) x(1,2) x(1,3) x(1,4) x(1,5) x(2,1) x(2,2) x(2,3) x(2,4) x(2,5) x(3,1) x(3,2) x(3,3) x(3,4) x(3,5) x(4,1) x(4,2) x(4,3) x(4,4) x(4,5) x(5,1) x(5,2) x(5,3) x(5,4) x(5,5) x(6,1) x(6,2) x(6,3) x(6,4) x(6,5) x(7,1) x (7,2) x(7,3) x(7,4) x(7,5)

end