CPLEXをPythonから呼ぶ(DOcplex)

1. はじめに

Qiita初投稿です。本記事は備忘録として記録し誤った箇所があるかもしれません。

IBM ILOGの提供する最適化ソリューションとしての開発環境はIBM ILOG CPLEX Optimization Studioと呼ばれています。
CPLEXの開発言語としてC/C++/Java/Python などがあげられ、他にもEclipseのPluginを用いたOPL言語を用いて最適化問題を記述することができます。
CPLEX Studioの統合開発環境(IDE)では、基本的にOPL言語を用いた開発とインタラクティブに最適化問題を解くことができる一方で、多目的最適化問題を解いたり、CPLEXで得た解をさらに別の問題に適用したりするような場面においては若干の使いづらさが見られるように思えます。
そこで今回はPython APIによる開発環境の構築を備忘録的に記録する意味を込めて、記事を書くに至ります。
ここで、CPLEX Python APIには大きく DOCplex[1]とPython-API(Legacy)[2]との2つが存在しますが、レガシー版は遠くない将来に廃止される予定らしいので、ここではDOCplexを用いた開発環境の構築を行います。

2. 動作環境

動作確認は
・Ubuntu 18.04 Bionic (64bit, 8GB, on VMWare)
・CPLEX Optimization Studio 12.9
・Python 3.7.3
にて行いました。

• 前提として、Pythonはインストール済とします。
  なお、Pythonは Python2*(≧Python2.7.9)　もしくは Python3*(≧ Python3.6) とします。
  (ただし、Python3.8以上は対応していないようです)
• 本記事ではpipやcondaを使用せずに環境を構築します。pip/condaでのインストールは既出なのでここでは触れません。

3. CPLEX Studio 12.9 のインストール手順

まずはCPLEXStudioをDLします。
サイト[3]から.binをダウンロードしておきます (~/Downloadsに置くとします)。
ダウンロードの方法ですが、[3]を読めば簡単にダウンロードできるのでここでは省略します。

ダウンロードが終わったら、インストールを開始していきましょう。
~/Downloadsに移動して作業することにします。

$cd ~/Downloads

まずは.binファイルに実行権限を与えます。

$chmod +x CPLEX_OPT_STUD_129_LNX_X86-64.bin

次に、.binファイルを実行します。

$sudo ./CPLEX_OPT_STUD_129_LNX_X86-64.bin

何らかの言語で、インストーラが立ち上がっていくつか質問をされます。
以下にまとめておきます。もし嫌になった場合は quit と叩けば止まります。

1. ローカルの選択: --> 1. English or 2. 日本語
2. インストール前に全てのプログラムを終了することをお勧めします: --> ENTER or back
3. インストールパスの指定: /opt/ibm/ILOG/CPLEX_Studio129がデフォルト
4. インストールするにはENTERキーを押してください: --> ENTER
5. ディスク容量の確認 (約2GB程度): --> ENTER
6. 正常にインストールが完了しました: --> ENTER

いくつかパスを通す必要があります。
CPLEXにはMathematical Programming (MP)と Constraint Programming (CP)の2種類の最適化エンジンが備わっており、それぞれバイナリパスが異なります。
シェルの設定ファイル(~/.bashrc)を開いて、最終行に続けて以下のexportを記述します。

$echo "export LD_LIBRARY_PATH="/opt/ibm/ILOG/CPLEX_Studio129/opl/bin/x86-64_linux:$LD_LIBRARY_PATH"
$echo "export PATH="/opt/ibm/ILOG/CPLEX_Studio129/opl/bin/x86-64_linux:$PATH"
$echo "export PATH="/opt/ibm/ILOG/CPLEX_Studio129/cplex/bin/x86-64_linux:$PATH"
$echo "export PATH="/opt/ibm/ILOG/CPLEX_Studio129/cpoptimizer/bin/x86-64_linux:$PATH"

追記したら、反映しておきます。

$source ~/.bashrc

ここで、コマンドが動くかを確認してみましょう。

$cplex
Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.9.0.0
with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2019. All Rights Reserved.
Type 'help' for a list of available commands.
Type 'help' followed by a command name for　more
information on commands.

制約プログラミングの最適化エンジンも起動して確認してみましょう。

$cpoptimizer
Welcome to IBM(R) ILOG(R) CP Interactive Optimizer 12.9.0.0
with Simplex, Mixed Integer & Barrier Optimizers
5724-Y48 5724-Y49 5724-Y54 5724-Y55 5724-A06 5724-A29
Copyright IBM Corp. 1990, 2019. All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for　more
information on commands.

また、パスが通っていれば以下のコマンドも通るはず。
ズラズラっとhelpの内容が表示されれば問題なくパスが通っています。

$oplrun

【もしこれで command not found が出たりなどしてうまく起動しなかったら】
LD_LIBRARY_PATHの設定が反映されない場合があるようです (OS依存でしょうか..?)。
共有ライブラリにパスを登録することで回避できます (この辺はあまりよくわかっていません...)。
/etc/ld.so.conf.d 以下にhogehoge.confというファイルを作成し、LD_LIBRARY_PATHを追記しておけば大丈夫そうです。

$sudo vim /etc/ld.so.conf.d/oplrun.conf

以下を中に書いておきます。

/opt/ibm/ILOG/CPLEX_Studio129/opl/bin/x86-64_linux/
/opt/ibm/ILOG/CPLEX_Studio129/cplex/bin/x86-64_linux/
/opt/ibm/ILOG/CPLEX_Studio129/cpoptimizer/bin/x86-64_linux/

ファイルを保存し、cacheを再構築しておきます。

$sudo ldconfig

4. DOCplexのセットアップ

本記事ではCPLEXを /opt/ibm/ILOG/CPLEX_Studio129/...にインストールしてきました。
以下、 /opt/ibm/ILOG/CPLEX_129 を (CPLEX_DIR) と置くことにします。
自身で任意のパスを設定した場合はCPLEX_DIRは別パスのはずです。注意してください。

(CPLEX_DIR)/python/docplex/ に移動するとsetup.pyというファイルがあるので、これを実行します。

$cd (CPLEX_DIR)/python/docplex
$sudo python3 setup.py install

セットアップが開始し、数秒のうちに終了します。
これでDOCplexの環境構築は終わりです。

5. 例題を解く

ここからは公式リファレンスのサンプル[4]を用いて簡単に書き方についても触れようと思います。
筆者自身が勉強中の身なのであやふやな箇所もありますが、何かしら貢献できれば幸いです。

ここでは、[4]の最初の例題 The Transportation Problem を取り上げようと思います。

これは、2拠点に置かれた物資を3拠点へと輸送する際のコストを最小化する問題です。
図は非負整数重み付きの有向非循環グラフ(DAG)です。
左側のOut-goingノードが示すのは物資を運び出すことができる拠点を示しています。
また、赤字で書かれた数は各ノードの重みであり、輸送可能な物資の総量を示します。
右側のIn-comingノードの横に緑字の数が示すのは拠点が要求する必要物資の総量です。
ノード間のアークが示すのは輸送可能な経路であり、アーク上の重みは物資1つあたりの輸送コストを示します

この問題において輸送コストを算出する上での組合せとしては、いくつか存在します。
これは単純な例題ですので、最適解は以下のように簡単に求まります。

ノード3はノード1からの物資以外は受け取れず，物資を7つを必要とします。
したがってノード1の物資15から物資7だけノード３へと送られるためノード1の残量は8となり、このとき物資7をノード3へ輸送コスト2で送るので2×7=14の輸送コストを要します。

同様にノード4はノード2からしか物資を受け取れないのでノード2の残物資量は20-10=10となり、このときの輸送コストは10×5=50となるので、ノード1残物資量は8、ノード2残物資量は10で、あとはノード5が15の物資を必要としている状態になります。
このとき、ノード2からノード5に対するの輸送コストが低いのでノード2から優先的に物資を運ぶことにすると，ノード2は10を全て運びきり残量が0，一方ノード5の必要物資は5となります。
最後にノード1から物資を5だけノード5へ送ることで全ての要求を満たせます。
ここでの過程で、ノード2が輸送コスト3で10運ぶので 10×3=30輸送コスト、ノード1が輸送コスト4で5だけ運ぶので5×4=20輸送コストを要する。

以上から、最終的に14+50+30+20=114だけの輸送コストが必要となります。

この問題を最適化問題として成立させるために目的関数と制約条件を整理し、決定変数を定義する必要があります。

• 目的関数: 総輸送コストを最小化する
• 制約条件1: 左側各ノードの輸出量が重みと等しいか、それより小さい
• 制約条件2: 右側各ノードの輸入量が重みをと等しいか、それより大きい

以上を踏まえると決定変数は以下にすると良さそうです。

• 決定変数: x (i , j): ノード_i_からノード_j_へ輸送する物資の量

以下でプログラムを書いていくことにします。

sample.py

 #URL/Keyを書くとクラウドで問題を解くことができます。
 #ここではローカル実行を想定しているのでNoneとします。
url=None
key=None

 #Preparation of data
 #ノード1は15, ノード2は20だけ物資を有する
capacities = {1:15, 2:20} 
 #ノード3は7, ノード4は10, ノード5は15の要求がある
demands = {3:7, 4:10, 5:15}
 #このときアークにおけるコストは (1,3)=2, (1,5)=4, (2,4)=5, (2,5)=3なので
costs = {(1,3):2, (1,5):4, (2,4):5, (2,5):3}
source = range(1,3) #pythonでは range(i,j)は i...j-1まで
target  = range(3,6)

 #description of a problem
 #docplexをインポートする
from docplex.mp.model import Model
tm = Model(name='transportation')

 #decision (continuous) variable 
 #変数x(i,j)を問題tmの中に定義する．xは連続変数でiはsource，jはtargetを参照する．ただしこれはcostsに存在する (アークが繋がっている者同士) 場合に限る．
x = {(i,j): tm.continuous_var(name='x_{0}_{1}'.format(i,j)) for i in source for j in target if (i,j) in costs}
tm.print_information()

 #add constraints
 # (1,3), (1,5) を運ぶ物資の総量がcapacities[1]  (=15)を超えない
 # (2,4), (2,5) を運ぶ物資の総量がcapacities[2]  (=20)を超えない
for i in source:
    tm.add_constraint(tm.sum(x[i,j] for j in target if (i,j) in costs) <= capacities[i] )
for j in target:
    tm.add_constraint(tm.sum(x[i,j] for i in source if (i,j) in costs) >= demands[j] )

 #Objective function
 #目的関数はアーク(i,j)間に係る輸送コストの総量の最小化
tm.minimize(tm.sum(x[i,j]*costs[i,j] for i in source for j in target if (i,j) in costs))

 #Solve
 #問題を解く
tms = tm.solve(url=url,key=key)

 #Display and exceptions
 #解を表示
assert tms
tms.display()

実行すると以下を得ます。

Model: transportation
 - number of variables: 4
   - binary=0, integer=0, continuous=4
 - number of constraints: 0
   - linear=0
 - parameters: defaults
solution for: transportation
objective: 114.000
x_1_3 = 7.000
x_1_5 = 5.000
x_2_4 = 10.000
x_2_5 = 10.000

DOCplex (Python-API) の導入はここまでです。

参考リンク

1: DOCplex公式リファレンス
2: Python-API(Legacy)
3: CPLEXダウンロード
4: DOCplex公式リファレンス - 例題