新数理計画法システムLocalSolverによる大規模組合せ最適化問題への適用 モデリングと実行

カテゴリ: 部門大会

論文No: TC8-3

グループ名: 【C】平成25年電気学会電子・情報・システム部門大会講演論文集

発行日: 2013/09/04

タイトル(英語): Solving Large-scale combitonal problem by LocalSolver - modeling and execution -

著者名: 宮崎 知明(ＭＳＩ),石村 猛(ＭＳＩ)

著者名(英語): Miyazaki Tomoaki(MSI Limited),Ishimura Takeshi(MSI Limited)

キーワード: 大規模組合せ問題|数理計画法システム|局所探索|数理最適化|large-scale combinatorial problem|mathematical programming system|local search|mathematical optimization

要約(日本語): 大規模組合せ最適化問題は、既存の数理計画法システム（MIP）や制約論理システム（CP）では、解探索で組合せ爆発が起こり、実用時間内に解くことは出来なかったのが現状である。
　新数理計画法システムLocalSolverは、解探索に組合せ爆発が起こらないよう、局所探索法をベースとしたシステムであり、１０００万以上の０ １整数変数を扱うことができる。
　本来、局所探索法によるシステムは問題対応型システムとなり、定式化及び解法が問題毎に異なっていることから、個別に時間をかけて開発する必要があった。
　Localsolverは大規模組合せ最適化問題を汎用的かつコンパクトに定式化できるモデル記述言語（LSP言語）を備えている。
　本稿では、LSP言語によるモデリングの考え方を紹介するとともに、複数の大規模組合せ最適化問題への適用事例を示す。

PDFファイルサイズ: 3,718 Kバイト