Pyomo+Ipopt+HSLソルバーで、非線形計画問題の環境構築

プログラミング

今回は、タイトル通り非線形計画問題を解くための環境構築を行います。
HSLソフバーを導入することで、研究でも使えるレベルの環境を準備します。

背景と目的

非線形計画問題は、最適化問題の一種で、多くの理系分野で出現する問題です。
ロボット制御や経路設計などで、この問題を解く必要がある場合が多いです。

非線形計画問題は、その目的関数と制約条件で表せられるため、問題を自動で解いてくれる仕組み(ソルバー)があると便利です。
そのため、様々な種類のソルバーが提供され、多くの言語で利用するためのライブラリが整理されています。

Pythonでこの手の最適化問題を扱うライブラリとして、Pyomoが有名です。
しかし、Pyomoにはソルバーが組み込まれておらず、様々なソルバーとのインターフェースが主な役割です。

そのため、非線形計画問題を解くためのソルバーを、別にインストールする必要があります。
そこで、通常はIPOPT(Interior Point OPTimizer)という無償のソルバーを利用します。

さらにIPOPT自体も内部処理に、外部パッケージとして別のソルバーを利用しています。
デフォルトでMUMPSというソルバーを利用していますが、大規模な問題を高速で解くのは向いていません。

そこで、MUMPSの代わりに、HSL (Harwell Subroutine Library)ソルバーを利用します。
ほとんどの大規模な問題において、HSLソルバーはMUMPSソフバーよりも圧倒的に速く解を得ることができます。

今回は、Pyomo + Ipopt + HSLを組み合わせた、非線形計画問題の最強環境を作り上げます!

前提

まずは前提条件を整理します。

  • OS: Mac/Linux
  • Python 3.x がインストール済み
  • pip3がインストール済み

PyomoとIpoptのインストール

pipcondaどちらを使ってもスムーズにインストールできます。

$ pip install pyomo ipopt

or

$ conda install -c conda-forge pyomo ipopt

HSLソルバーのダウンロード

HSLが提供するソルバーは、下記のサイトから自分で申請してダウンロードリンクを送ってもらう必要があります。

HSL for IPOPT
HSL support for the COIN-OR IPOPT nonlinear solver

まずはリンク先から画像右下の最新版を選択します。

次に、利用目的を聞かれるので、上側の「アカデミック」を選択します。

選択すると、利用規約と個人情報の入力が求められるので、すべてフォームを入力します。
最後の利用先については、「I want to use the solvers for trajectory optimization.」っていう感じでテキトーに書きました。
全ての項目を入力したら、「Accept」ボタンを押します。

以下のような画面が出れば、終了です。
申請完了メールなどは、特に来ないです。

3日くらいで、申請受理のメールが来きます。
メールのリンク先から、tarファイル(coinhsl-2019.05.21.tar.gz)をダウンロードします。

HSLソルバーのインストール

まずは、ビルドツールをダウンロードします。

$ sudo apt-get update
$ sudo apt-get install -y gcc g++ gfortran git patch wget pkg-config liblapack-dev libmetis-dev build-essential

インストールには、coinbrewというツールを使うのが一番簡単です。
その準備のため、適当なフォルダに、ダウンロードしたcoinhsl-2019.05.21.tar.gzを移動させます。
このフォルダ内に、ビルドに必要なファイルが追加されていくので、空のフォルダを用意することをおすすめします。

$ cd [適当なフォルダ]/
$ ls
coinhsl-2019.05.21.tar.gz

coinbrewをダウンロードし、実行権限を与えます。

$ wget https://raw.githubusercontent.com/coin-or/coinbrew/master/coinbrew
$ chmod u+x coinbrew

coinbrewを使って、Ipoptをフェッチします。

$ ./coinbrew fetch Ipopt --no-prompt

ダウンロードしたcoinhsl-2019.05.21.tar.gzを展開して、適当なフォルダ位置に移動させます。

$ tar -xvzf coinhsl-2019.05.21.tar.gz
$ mv coinhsl-2019.05.21 ThirdParty/HSL/coinhsl

そうすると、以下のようなフォルダ構造になるはずです。

[適当なフォルダ]
├── coinbrew
├── coinhsl-2015.06.23.tar.gz
├── Ipopt
└── ThirdParty
    ├── ASL
    ├── HSL
    │   └── coinhsl
    └── Mumps

フォルダ構造が確認できれば、あとはビルドしてインストールをします。

$ ./coinbrew build Ipopt --prefix=build --test --no-prompt --verbosity=3
...
Install completed. If executing any of the installed
binaries results in an error that shared libraries cannot
be found, you may need to
  - add 'export LD_LIBRARY_PATH=/home/alex/Projects/aru-docs/tmp/coinbrew-install/./build/lib' to your ~/.bashrc (Linux)
  - add 'export DYLD_LIBRARY_PATH=/home/alex/Projects/aru-docs/tmp/coinbrew-install/./build/lib' to ~/.bashrc (OS X)

最後に、表示されているのように、リンクの設定を行います。
Linuxであれば、

$ export LD_LIBRARY_PATH=/[適当なフォルダ]/build/lib

Macであれば、

$ export DYLD_LIBRARY_PATH=/[適当なフォルダ]/build/lib

これでインストール完了です!

動作確認

最後にPyomoを使って、PythonからHSLが提供するMA86というソルバーを使ってみましょう。
以下のソースコードをtest.pyという名前で保存します。

import pyomo.environ as pyo
from pyomo.opt import SolverFactory

def create_new_model():
    model = pyo.ConcreteModel()
    model.x = pyo.Var([1,2], domain=pyo.NonNegativeReals)
    model.OBJ = pyo.Objective(expr = 2*model.x[1] + 3*model.x[2])
    model.Constraint1 = pyo.Constraint(expr = 3*model.x[1] + 4*model.x[2] >= 1)
    return model

opt = SolverFactory('ipopt', executable='build/bin/ipopt')
opt.solve(create_new_model())
opt.options['linear_solver'] = 'ma86'
opt.options['OF_ma86_scaling'] = 'none'  # a random parameter

opt.solve(create_new_model(), tee=True)

これを実行すれば、以下のような結果が表示されれば、成功です!

$ python test.py
Ipopt 3.14.2: linear_solver=ma86
option_file_name=/tmp/tmpkqxqsvyu_ipopt.opt

Using option file "/tmp/tmpkqxqsvyu_ipopt.opt".

******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
 Ipopt is released as open source code under the Eclipse Public License (EPL).
         For more information visit https://github.com/coin-or/Ipopt
******************************************************************************

This is Ipopt version 3.14.2, running with linear solver ma86.

Number of nonzeros in equality constraint Jacobian...:        0
Number of nonzeros in inequality constraint Jacobian.:        2
Number of nonzeros in Lagrangian Hessian.............:        0

Total number of variables............................:        2
                     variables with only lower bounds:        2
                variables with lower and upper bounds:        0
                     variables with only upper bounds:        0
Total number of equality constraints.................:        0
Total number of inequality constraints...............:        1
        inequality constraints with only lower bounds:        1
   inequality constraints with lower and upper bounds:        0
        inequality constraints with only upper bounds:        0

iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
   0  4.9999950e-02 9.30e-01 5.38e-01  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1  4.0516238e-01 4.36e-01 6.12e+00  -1.7 1.44e-01    -  7.40e-02 5.36e-01h  1
   2  7.1525760e-01 0.00e+00 1.42e-01  -1.7 1.17e-01    -  7.26e-01 1.00e+00h  1
   3  6.7446175e-01 0.00e+00 5.92e-02  -2.5 2.87e-01    -  1.00e+00 5.15e-01f  1
   4  6.7220463e-01 0.00e+00 2.83e-08  -2.5 1.28e-02    -  1.00e+00 1.00e+00f  1
   5  6.6704072e-01 0.00e+00 1.50e-09  -3.8 8.53e-03    -  1.00e+00 1.00e+00f  1
   6  6.6667054e-01 0.00e+00 1.84e-11  -5.7 8.64e-04    -  1.00e+00 1.00e+00f  1
   7  6.6666666e-01 0.00e+00 2.53e-14  -8.6 7.30e-06    -  1.00e+00 1.00e+00f  1

Number of Iterations....: 7

                                   (scaled)                 (unscaled)
Objective...............:   6.6666666171454159e-01    6.6666666171454159e-01
Dual infeasibility......:   2.5257573810222311e-14    2.5257573810222311e-14
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Variable bound violation:   2.3605492901504038e-09    2.3605492901504038e-09
Complementarity.........:   2.5464836454225496e-09    2.5464836454225496e-09
Overall NLP error.......:   2.5464836454225496e-09    2.5464836454225496e-09

Number of objective function evaluations             = 8
Number of objective gradient evaluations             = 8
Number of equality constraint evaluations            = 0
Number of inequality constraint evaluations          = 8
Number of equality constraint Jacobian evaluations   = 0
Number of inequality constraint Jacobian evaluations = 8
Number of Lagrangian Hessian evaluations             = 7
Total seconds in IPOPT                               = 0.267

EXIT: Optimal Solution Found.

まとめ

今回は、HSLが提供するソルバーを用いた環境構築の解説をしました。

HSLのソルバーは申請作業があるので、入手は面倒ですが、一度手に入れれば非常に便利です。

教科書に載っているような問題であれば、Ipoptについてくるデフォルトのソルバーで十分ですが、
研究などで大規模な非線形計画問題を解く際には、HSLなどのソルバーを利用する必要があります。

この記事が皆様のお役に立てれば幸いです。

コメント

タイトルとURLをコピーしました