メタヒューリスティクスによる汎用整数計画ソルバーの開発

はじめに
開発したソルバーの概要と特徴
使い方
ドキュメント
ベンチマーク
ライセンス
おわりに
参考文献
修正履歴

はじめに

メタヒューリスティクスベースの整数計画ソルバーをC++で開発しています．性能面・機能面ともに改善の余地はまだまだあるのですが，当初自分が思い描いたものがだいぶかたちになってきたということもあり，一度ご紹介したいと思います．

プログラムはオープンソースとして開発しており，ソースコード・ドキュメントは以下のGithub リポジトリで管理しています． github.com

開発したソルバーの概要と特徴

PRINTEMPS は，C++で設計・実装された線形／非線形整数計画問題を近似的に解く汎用モデラー／ソルバーです*1．アルゴリズムとしてはメタヒューリスティクス，具体的には文献[1]で提案されているペナルティ係数を動的に調整するタブーサーチ法を採用しており*2，分枝限定法に基づくMIPソルバーで解けない問題群に対し，厳密解にこだわらず「そこそこ良い解」を得たい局面での適用を想定しています*3．また前処理による変数・制約条件の除去や補助メモリを用いた高速な近傍解評価，解改善の見込みのない近傍操作の事前除去など，計算効率化の手法も取り入れています．

PRINTEMPSの特徴は以下のとおりです．

可搬性：ヘッダオンリーライブラリとして実装されており，他の商用あるいはオープンソースライブラリにも依存していないため，必要なヘッダファイルを単純にコピーするだけで自作プログラムに組み込むことが可能
モデリングの直観性：ソルバーとあわせてモデリング環境も提供しており，プログラム上で数式を記述するかたちで問題のモデリングが可能*4
近傍定義の拡張性：変数や問題構造に応じて適切な近傍定義*5を自動的に抽出するほか，ユーザ定義の近傍を採用することも可能

使い方

ダウンロード

上述のGithub リポジトリのmasterブランチをCloneしていただくか，Releaseから最新アーカイブをダウンロードします．

インストール

リポジトリ直下（あるいはアーカイブを解凍して展開されるディレクトリの直下）にあるprintempsディレクトリ以下を適当な場所にコピーしていただければOKです．

サンプル

サンプルとして，以下のような簡単な整数計画問題[2]を考えます： \begin{split} \mathrm{(P1)}: &\underset{x}{\mathrm{minimize}} \enspace &&&x_1 + 10 &x_2 \\ &\mathrm{subject\,to} \enspace &&66\, &x_1 + 14 &x_2 \ge 1430, \\ &&-&82\, &x_1 + 28 &x_2 \ge 1306, \end{split} $$ \qquad x_1, x_2 \in \mathbb{Z}. $$ 本問題をPRINTEMPSを用いてモデリング・求解するコードは以下のとおりとなります．

#include <printemps.h>
int main(void) {
    // (1) モデリング
    printemps::model::IPModel model;

    auto& x = model.create_variables("x", 2);
    auto& g = model.create_constraints("g", 2);

    g(0) =  66 * x(0) + 14 * x(1) >= 1430;
    g(1) = -82 * x(0) + 28 * x(1) >= 1306;
    model.minimize(x(0) + 10 * x(1));

    // (2) ソルバー実行（最適化）
    auto result = printemps::solver::solve(&model);

    // (3) 計算結果へのアクセス
    auto objective = result.solution.objective();
    auto variables = result.solution.variables("x");
    std::cout << "objective = " << objective << std::endl;
    std::cout << "x(0) = " << variables.values(0) << std::endl;
    std::cout << "x(1) = " << variables.values(1) << std::endl;

    return 0;
}

上のコードをコンパイルして実行すると以下の結果が標準出力として得られます．

objective = 707
x(0) = 7
x(1) = 70

リポジトリにはこのほかにもナップサック問題，ビンパッキング問題，数独，2次割当問題のサンプルを用意しています．example/ディレクトリ以下をご参照ください．モデリングを効率よくおこなうため，上のサンプル内で用いた記述法のみならず，複数の変数の和や，パラメータベクトルと変数ベクトルの内積などに対する簡単な記述法も備えています．

コンパイル

C++17に対応したC++コンパイラであればプラットフォームによらずコンパイル可能です（ただし以下の説明ではLinux, macOSを想定します）．たとえば，リポジトリに含まれるsample/knapsack.cppをg++を用いてコンパイル・ビルドする場合は以下のコマンドを実行します．

$g++ -std=c++17 -O3 -I path/to/printemps [-fopenmp] sample/knapsack.cpp -o knapsack.exe

ただしpath/to/printempsはPRINTEMPSのインストール先ディレクトリです．OpenMP有効化フラグ[-fopenmp]は必須でありませんが，マルチコア環境下ではこれを有効化することで近傍操作生成・近傍解評価などが並列化され，計算時間が短縮されます．

オプション・パラメータ設定

Solver Option Guideに示すとおり，PRINTEMPSには多数のオプション・パラメータがありますが，基本的には下表に示す計算時間や表示形式に係る項目の調整でじゅうぶんと思います．

オプション名	型	デフォルト	説明
`iteration_max`	`int`	`100`	全体でのタブーサーチの外側反復回数
`time_max`	`double`	`120.0`	全体での計算時間制限[sec]
`output.verbose`	`printemps::option::verbose`	`None`	標準出力へのログ出力レベル `None`:なにも表示しない `Warning`: 警告のみ表示 `Outer`:警告に加え，各タブーサーチの外側反復の結果を表示 `Full`:タブーサーチの内側反復の結果も含めすべて表示

スタンドアロンソルバー

整数変数のみを含むMPS(Mathematical Programming System)ファイルに記述された問題を解くスタンドアロンソルバーも用意しており，以下のコマンドでコンパイル・ビルド可能です*6 ．

$g++ -std=c++17 -O3 -I path/to/printemps [-fopenmp] application/mps_solver/main.cpp -o mps_solver.exe

ただしpath/to/printempsはそれぞれPRINTEMPSのインストール先ディレクトリです．ビルドして得られたソルバーを用いてMPSファイルに記述された最適化問題の求解をおこなう場合，以下のコマンドを実行します．

$./mps_solver.exe mps_file [-p option_file]

mps_fileは解きたい問題が記述されたMPSファイルのパスです．-p option_fileは任意であり，オプション・パラメータをJSONファイル経由で指定できます．必要に応じて以下のJSONをテンプレートとしてお使いください．

{
    "iteration_max": 100,
    "time_max": 120.0,
    "output": {
        "verbose": "Off"
    }
}

ドキュメント

ドキュメントとして以下の2つを用意しています．

Starter Guide：全体にわたっての使用方法として，モデリング方法，最適化計算実行方法，計算結果へのアクセス方法について記述したもの
Solver Option Guide：オプションの一覧とその説明・デフォルト値について示したもの

非線形の目的関数・制約条件の定義方法や，ユーザ定義の近傍の定義方法については申し訳ありませんがStarter Guideには未記載です．これらを使用した計算をおこなう場合，2次割当問題のサンプルをご参考としていただければ幸いです．

ベンチマーク

MIPLIB 2017の整数計画問題インスタンスを用いた性能ベンチマークもおこなっています．詳細なベンチマーク結果についてはこちらをご参照ください．

ライセンス

MITライセンスでの配布としています．

おわりに

PRINTEMPSはおもに実務における数理最適化業務を効率化することを目的として開発しています．数理最適化の業務は，

Step 1: 実問題を最適化問題としてモデリング（定式化）し，
Step 2: アルゴリズムを開発して（あるいはソルバーを用いて）問題を解き，
Step 3: 得られた解を検証し，問題がなければ解をなんらかのかたちで実行する．そうでなければStep 1へ戻る．

というプロセスを経ることが多いです．このプロセスが一回で完了することは稀であり，ほとんどの場合，解の検証で明らかになった制約条件の抜け漏れ反映などにより，Step 1〜Step 3のプロセスを複数回繰り返すこととなります．ここでStep 2の求解に際して，定式化された問題が分枝限定法ベースの汎用ソルバーで容易に解ける問題であるのならばよいのですが，実務では分枝限定法では手に負えない「厄介な」構造*7をもつ問題も多く見られます．このような問題たちに対して，とくに検討の端緒において，専用アルゴリズムを設計・実装するなどの手間をかけずに「そこそこの解」を求めたい，という局面は頻繁にあります．PRINTEMPSはこのような局面を想定して開発したソルバーであり，とくに「手軽さ」と「汎用性」を重視した作りとなっています．

現状では性能や速度については改善の余地も大きく，集合分割問題など等式制約条件を多く含む問題に弱いなどの弱点もありますが，引き続き頑張って改良を進めていきます！*8

参考文献

[1] K.Nonobe and T.Ibaraki: An improved tabu search method for the weighted constraint satisfaction problem, INFOR Vol.39, No.2 pp.131–151 (2001).
[2] R.Fletcher: Practical Methods of Optimization, Second Edition, John Wiley & Sons (2000).

修正履歴

2020/11/24 ソフトウェア名の変更に伴い記述を変更しました．またMIPLIB 2017のオープンインスタンス暫定値更新に関して注記を加筆しました．
2020/12/1 章構成を修正しつつ，ベンチマーク結果について加筆しました．
2020/12/5 本文の記述を微修正しました。また本ソルバを使う上での定式化のポイントについて注記を加筆しました．
2021/4/22 v1.6.0バージョンアップにあわせて内容を改訂しました。
2021/6/27 v1.6.3バージョンアップにあわせて内容を改訂しました。
2022/8/31 v2.0.0バージョンアップにあわせて内容を改訂しました。

*1:ただし，高速化処理など多くの工夫は線形整数計画問題に特化するかたちで実装されており，特段の理由がなければ線形整数計画としてモデリング・求解することをおすすめします．

*2:商用ソルバーとしてはNTTデータ数理システムのNumerical Optimizerも同法に基づいたアルゴリズムを提供しています．当然ながら本ソルバーよりも高性能です．

*3:ただし，MIPソルバーが得意とする定式化と本ソルバーが得意とする定式化はかならずしも同じではありません．本ソルバーを用いる場合，等式制約条件をなるべく使わない定式化が望ましいです．

*4:モデリングの仕様についてはSIMPLEとPuLPの影響を受けています．

*5:0-1変数については1-flip近傍，その他整数変数については±1近傍および(最大値(最小値)+現在値)/2近傍が自動的に定義されており，これらがデフォルト近傍となります．このほかにもMIPLIB2017の制約条件区分に記載されたAggregation, Precedence, Variable Bound, Set Partitioningなど特殊な構造の制約条件が存在する場合，これらに特化した近傍が追加されます．ただし，問題によっては近傍数が莫大となるので，デフォルトでは一部の近傍はオフとしています．

*6:MakeおよびCMakeがインストールされた環境下では「$make -f makefile/Makefile.application」を実行すれば簡易にコンパイル・ビルドできます．

*7:たとえば「最大値最小化」とか「平準化」とか…．

*8:改良のなかでMIPLIB 2017のオープンインスタンスのひとつであるcdc 7-4-3-2, scpj4scip, scpl4, scpm1, scpn2の暫定値を更新しており，また他の複数のインスタンスに対しても既知の暫定解と同等の解を得ることに成功しています．