CasADiとBONMINで混合整数非線形計画問題を解く

※記事内に商品プロモーションを含むことがあります。

はじめに

CasADiは自動微分と非線形最適化のためのライブラリである。C++で実装されており、C++, Python, Matlab, Octaveのインターフェースを備えている。
本記事ではPythonを使い、CasADiで混合整数非線形最適化問題 (MINLP) を解く方法をまとめた。

CasADiにはBONMINというMINLPソルバが含まれているため、これを用いる。問題が非凸の場合、BONMINはヒューリスティックに最適解を求めるが、大域的最適解が得られるとは限らない。

CasADiの基本的な使い方は以下の記事を参考。
CasADiとIPOPTで非線形計画問題を解く

環境は以下の通り。

Python 3.7.4
CasADi 3.5.5

リンク

対象とする混合整数非線形計画問題

以下の混合整数非線形最小化問題を考える。

$$ \begin{array}{ll} \text{minimize} & f(x_1, x_2) = (x_1-0.8)^2 + (x_2-0.7)^2 \\ & x_1 \in \mathbb{R}, x_2 \in \mathbb{Z} \end{array} $$

すなわち、$x_1$は実数、$x_2$は整数である。
この問題は、$(x_1, x_2)=(0.8, 1)$で最小値$0.09$をとる。

CasADiのソースコード

上記の問題をCasADiを使って記述し、最適化を実行したコードは以下のようになる。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import casadi
opti = casadi.Opti()

# 変数を定義
x1 = opti.variable()
x2 = opti.variable()

# 目的関数を定義
OBJ = (x1-0.8)**2 + (x2-0.7)**2
opti.minimize(OBJ)

p_opts = {'discrete': [False, True]}
s_opts = {'time_limit': 100}
opti.solver('bonmin', p_opts, s_opts) # 最適化ソルバを設定
sol = opti.solve() # 最適化計算を実行

print(f'評価関数：{sol.value(OBJ)}')
print(f'x1: {sol.value(x1)}')
print(f'x2: {sol.value(x2)}')

実行結果は以下のようになり、最適値を得られている。

NLP0012I 
              Num      Status      Obj             It       time                 Location
NLP0014I             1         OPT 0        1 0
NLP0014I             2         OPT 0.48999999        3 0.016
（中略）
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
      solver  :   t_proc      (avg)   t_wall      (avg)    n_eval
       nlp_f  |        0 (       0)        0 (       0)        19
  nlp_grad_f  |        0 (       0)        0 (       0)        30
  nlp_hess_l  |        0 (       0)        0 (       0)        13
       total  |  16.00ms ( 16.00ms)  15.62ms ( 15.62ms)         1
評価関数：0.09000000000000002
x1: 0.8
x2: 1.0

整数変数の指定

どの変数が整数か指定するには、solverメソッドの2番目の引数に与える。以下のようにキーをdiscreteとして、実数変数をFalse, 整数変数をtrueで指定する。

1
2
3


p_opts = {'discrete': [False, True]}
s_opts = {'time_limit': 100}
opti.solver('bonmin', p_opts, s_opts) # 最適化ソルバを設定

なお、s_optsは最適化ソルバ (BONMIN) に与えるオプションであり、3番目の引数とする。

IPOPTで設定可能なオプションについては以下のページを参照。
BONMIN Users' Manual - List of bonmin options

参考

CasADiの公式リファレンス