こんにちは。フロンドエンドエンジニアインターンの@takewakaです。
この記事はVASILY Advent Calendar 2017 18日目の記事になります。
この記事では業務から離れ、整数計画ソルバーCPLEXを用いて整数計画問題を簡単に解きます。
はじめに
ウェブ界隈ではあまり耳にしない最適化問題ですが、乗り換え案内や、恋愛アプリのマッチングなどで活用されているそうです。
そこで、アルゴリズムの知識がない人が最適化問題を解く選択肢としてソルバーの使用を提案します。
具体的には、簡単なナップサック問題をCPLEXと動的計画法の2種類で解いて比較します。
CPLEXとは
CPLEXは、IBM社が提供する商用の数理最適化ソフトウェアです。（アカデミック版は無料）
使用可能な言語はC, C++, Javaの3つです。今回はC++を使います。
以下の問題を解くことができます。
- 線形計画問題
- 2次計画問題
- 2次制約計画問題
- 混合整数計画問題
CPLEXのクラス群
ここでは、今回整数計画問題を解くに当たって必要となるCPLEXのクラスを説明します。
IloEnv
CPLEXの環境を構築するクラスで、このクラスのインスタンスはCPLEXを利用するにあたって最初に生成されるオブジェクトです。
他のCPLEXオブジェクトに最適化されたメモリ管理を提供します。
このクラスによるメモリ管理はOSのメモリ管理よりパフォーマンスいいそうです。
また、他のクラスのインスタンスを生成する時に引数として渡されます。
IloModel
最適化問題を定義するクラスです。
このクラスのインスタンスに目的関数、制約式、変数を格納します。
格納する際はaddメソッドを使います。
モデルを形成するにあたって最も重要な3つのクラスが以下になります。↓
IloObjective ・・・ 目的関数クラス
IloNumVar ・・・ 変数クラス
IloRange ・・・ 制約式クラス
今回は、目的関数を最大化したいのでIloMaximizeを使います。
また、整数変数を取り扱うのでIloIntVarを使います。（IloNumVarでもILOINTを引数に持たせればいけます）
IloCplex
最適化問題を解くクラスです。
ショートカットとして、引数にIloEnvの代わりにIloModelを取ることができます。
getObjValueメソッドで目的関数値を取得します。
getValuesメソッドで最適解を取得します。
ナップサック問題
容量$C$のナップサックが一つと、$n$種類の品物（各々、価値 $p_i$, 容積 $c_i$）が与えられたとき、ナップサックの容量$C$を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか
今回解く例題では
$N=5$
$C=6$
$(c_i,p_i)=(2,3),(3,2),(1,2),(2,4),(3,3)$
とします。
また簡単のため、同じ種類の品物を1つまでしか入れられないとします。
この時、目的関数は
最大化 $3x_1 + 2x_2 + 2x_3 + 4x_4 + 3x_5$
制約式は
$2x_1 + 3x_2 + 1x_3 + 2x_4 + 3x_5 <= 6$
$x_i ∈ {0, 1} i=1,2,3,4,5$
です。
CPLEXを用いたプログラム
#include<ilcplex/ilocplex.h>
using namespace std;
int main() {
IloEnv env;
IloModel model(env);
IloNumVarArray vars(env);
vars.add(IloIntVar(env, 0, 1));
vars.add(IloIntVar(env, 0, 1));
vars.add(IloIntVar(env, 0, 1));
vars.add(IloIntVar(env, 0, 1));
vars.add(IloIntVar(env, 0, 1));
model.add(IloMaximize(env, 3*vars[0] + 2*vars[1] + 2*vars[2] + 4*vars[3] + 3*vars[4]));
model.add( 2*vars[0] + 3*vars[1] + 1*vars[2] + 2*vars[3] + 3*vars[4] <= 6);
IloCplex cplex(model);
IloNumArray vals(env);
cplex.solve();
cplex.getValues(vals, vars);
env.out() << "Solution Value = " << cplex.getObjValue() << endl;
env.out() << "Values = " << vals << endl;
env.end();
return 0;
}
とっても直感的な書き方ができます。
アルゴリズムの知識も一切必要ないです。
動的計画法を用いたプログラム
#include<iostream>
using namespace std;
int N = 5;
int C = 6;
int c[5] = {2,3,1,2,3};
int p[5] = {3,2,2,4,3};
int solve() {
int dp[N + 1][C + 1];
for(int i = 0; i < C; i++) dp[0][i] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= C; j++) {
if ( j < c[i] ) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = max(dp[i][j], dp[i][j - c[i]] + p[i]);
}
}
}
return dp[N][C];
}
int main() {
cout << solve() << endl;
return 0;
}
他にも解く方法はありますが擬似多項式時間で解こうとするとこうなります。
アルゴリスムの知識がないと、何をやっているのか検討もつかないと思います。
まとめ
数理最適化問題のソルバーCPLEXの紹介でした。
簡単に問題が解けつつ、オリジナルで実装するアルゴリズムより圧倒的に速いはずなので興味があれば触ってみる価値はあると思います。
今回扱った問題は規模が小さすぎたので速さの恩恵は残念ながら感じられませんでしたけど。。
WebAssemblyの台頭もあってクライアントサイドでも何かを計算する機会がこれから出てきそうです。
そうなっていつかCPLEXをブラウザで動かすなんてことになったら熱いです。
参考にしたもの