テクノロジー

LocalSolverは大規模組合せ最適化問題を解くのに適した、史上初、ローカルサーチ法をベースとした数理計画法システムです。
LocalSolverでは数百万の0-1意思決定変数を持つ組合せ最適化問題のモデルを解くことができます。
ここではLocalSolverの主な技術的概念、特にLocalSolverが既存の数理計画法ソルバーよりも大規模組合せ最適化問題を解くパフォーマンスが何故優れているのかについて概要を説明します。

何故、LocalSolver?

近年、混合整数計画法または制約論理プログラミングのほとんどがツリー探索(TS)をベースにしています。ツリー探索テクニック（分枝限定法、分枝カット法、Branch-cut-price)では解空間の中で解を決定する整数変数を順番に決めていきます。
指数時間の計算を必要とするツリー探査の欠点は小規模または中規模の問題に限定されていることです。
：ツリー探索は整数変数の数を拡大することができないだけではなく、実用時間内に解が得られるとは限りません。
もしも終了しなければ、ツリー探索はヒューリスティックなアプローチよりもソリューションに対する保証がないと言わざるを得ません。
実際に、何千もの0-1意思決定変数を含む実世界の問題の多くでは、ツリー探索で数時間の計算時間を費やしてもなお、探索領域を絞り込むことができず、実行可能解の発見に失敗するケースが多く発生します。

対照的にローカルサーチ法では目的関数を改善するように"ムーブ"と呼ばれる計算コストをかけないでイタレーションを行います。このため、短時間の実行時間で高品質なソリューションを得ることが可能なためローカルサーチ法は専門家の間では高く評価されています。（数分または数秒）
一般的にはローカルサーチ法を現実世界の問題に適用するのは、簡単ではありません。
アルゴリズムの知識とコンピュータプログラミング技術の双方を必要とするため、専門的なアルゴリズム部分で"ムーブ"をどう評価するかが非常に困難です。
このように、組合せ最適化問題に対して汎用的に、ローカルサーチを組み込むことは長年の課題でした。（従来の古典的なローカルサーチ法をベースとする問題対応型モデリング＆実行ソルバーでは効果的ではありません。）

この課題について5年間のR＆Dプロジェクトの結果、LocalSolverチームはこの難題を可能にする技術の発見に成功しました。
LocalSolverは史上初、ローカルサーチ法による次世代・数理計画法システムです。
LocalSolverは自律的かつ革新的な"ムーブ"及び計算コストができるだけ小さくなるように高度に最適化した目的関数評価の機能を持ちます。
LocalSolverは100万以上の意思決定を持つ問題を数分の計算時間で高品質なソリューションを求めることができます。
現時点では、LocalSolverは求まった解に関しての保証を提供できませんが、実践において、特に現実世界のアプリケーションではLocalSolverは準最適解を求めることができます。
例えばROADEF/EURO2012 Challengeでのグーグル社の機械の配置問題でLocalSolverはたった一日でモデリングから最適化実行まで実現できたとして認められた唯一のソルバーです。

どのように動作するか

解探索LocalSolverのアプローチは下記の基本的概念に基づいています：
ローカルサーチ法を汎用的な組合せ最適化問題に適用できることを目的としています。
これは既存のローカルサーチ法をフレームワークやソルバー自体に組み込む試みと比較すると大きく異なる点です。
LocalSolverはイタレーションを進めるごとに実行可能解を改善することができるように構造化されたムーブを実行します。
さらにモデル記述で使用する算術演算子による制約条件によってムーブの評価を高度化します。
最終的にはLocalSolverはヒューリスティックな探索としてシュミレーティドアニーリング手法を使用しています。
この実行中に行われるメタ・ヒューリスティックなセルフチューニングは困難なムーブを可能にし、潜在的に、局所最適解の領域に入り込んでも別の探索領域に移ることを可能にします。
マルチスレッティングにおいて（デフォルトで起動）、複数の探索を並列的に実行し、最も期待できる探索領域に集中するように、随時、同期をとります。

LocalSolverに関する詳細情報
www.localsolver.com

このページの先頭へ