1. LocalSolverホーム
  2. LocalSolver 技術関連情報
  3. LocalSolverの解法(概要)

LocalSolver 技術関連情報

LocalSolverの解法(概要)by Frederic Gardi (2012.08)

1)LocalSolverは2段階で問題を解く:実行可能解の探索を行ったのち、最適化を行います。この2段階工程はLocal search法をベースとしています。

ユーザーモデルが、わずかな解しか持たないようにモデル化されている場合、(満足問題=制約問題が十分でない)当然、LocalSolverが実行可能解を探索するには、時間がかかります。しかし、ユーザーモデルが最適化問題として正しくモデル化されている場合、LocalSolverは実行可能解を数分から数秒で発見し、その後、すぐさまモデルの最適化を実行します。LocalSolverの主な目的は、満たされる見込みのないビジネス制約をユーザーが緩和することを支援し、汎用的な最適化問題としてユーザーの問題をモデル化することです。

ビジネスという観点から考えると、「解が見つからない」という答えに関心はありません。LocalSolverは実行不可能解を証明するために役立つわけではありません。現時点では、最適性の証明よりも難しい場合さえあります。:実行不可能解を証明したい場合は、既存ソルバーの使用を推奨します。

2)LocalSolverはLocal search法および、特に、我々の研究で開発された強力なLocal-search技術をベースとしています。

我々の認識では、Local search法をベースとした問題対応型のモデリング&実行ではない0-1プログラミングソルバーは存在しますが、LocalSolverのように、使いやすいモデリング言語と実行環境を備えたソルバーは、史上初であり、LocalSolverはLocal search法による次世代―数理計画法システムです。LocalSolverはlocal-search法の専門家がlocal-search法のアルゴリズムを記述する際に、イタレーションが困難だと感じるムーブでも実行することが可能です。

同様に、LocalSolver内の増分アルゴリズム部分が高度に最適化されたことで、専門的なヒューリスティクスさえもLocalSolverには及ばないことがあります。LocalSolverは国際的なORコンペで、80チーム中25位にランクし、全て専門的なアルゴリズムで記述された問題をたった一日でモデリングから最適化実行までを実現できたとして認められた唯一のソルバーです。(ここにニュースへのジャンプリンク)

3)LocalSolverはデフォルトでマルチスレッディングを提供しています。(追加的な費用は不要)

LocalSolverは1つのスレッドを使用する場合でも、高度な自律性および高品質なソリューションを提供するように設計されていますが、言うまでもなく、スレッド数を増加させれば、より高品質な解の提供が可能になります。当然、多くのコアを使用することで、必要不可欠であるロバスト性もさらに向上します。

このページの先頭へ