制約最適化ソルバーSCOP

パンフレット) 最適化ソルバー紹介資料(まとめ)  

概要

制約最適化ソルバー SCOP (Solver for  COnstraint Programing:スコープ) は,大規模な制約計画問題を高速に解くためのソルバーです.
ここでの制約計画(constraint programming)とは,従来の数理計画(gurobiなどの数理最適化ソルバーは数理計画ソルバー)を補完する最適化理論の体系です.
SCOPは,組合せ最適化問題に特化した求解原理を用いるため,従来の数理計画ソルバーで解けない大規模な組合せ最適化問題に対しても, 効率的に良好な解を探索します.

  

ベンチマーク結果

時間割作成第2回国際コンペテーションITC2007: Track1(試験時間割):3位,Track2(大学時間割):2位,Track3(高校時間割):3位 (3トラック全てで3位以内に入ったのはSCOPのもとになったアルゴリズムだけ)

ナーススケジューリングシフト作成第1回国際コンペテーションINRC 2010:Track1(10秒):2位,Track2(10分):3位,Track3(10時間):4位 

特徴

  • 世界的に有名な最適化理論の研究者である茨木先生(京都大学名誉教授)と野々部先生(法政大学)の開発したメタヒューリスティクスを基礎としているため,世界最速クラスの探索能力を有します.そのため,超大規模な問題でも,限られた計算時間内に,極めて効率的に求解することができます.
  • 数理最適化ソルバーと異なる方法で変数を定義するため,大幅に変数を減らすことができ,高速な求解が可能です.
  • 数理最適化ソルバーより(人が理解しやすい)自然な論理制約記述が可能です.
  • 大規模な問題でも,限られた計算時間内に,極めて効率的に求解することがでます.
  • 簡易モデリング言語によるデータ入力とPython言語インターフェイスを用意しています.
  • ユーザが計算時間を設定可能で,設定した計算時間内で最も良い解を出す仕組みです.

  

適用可能問題

幅広い組合せ最適化問題を解くことが可能です.特に,割当問題に対しては,人が理解しやすい非常に自然なモデリングが可能で,高速に良い答えを出すことが可能です.
人員配置最適化
会議スケジューリング
仕事割当
部屋の割当
生産最適化
投入順決定
広告割当 など

人員配置最適化では,シフトと業務を同時に考慮した最適化(割り当てられたシフトの中でどの業務を何時から何時まで行うかを決める問題)でも高速で良い答えを出すことが可能です.日単位や3交代制などのシフト作成より大分難しい問題で,シフトを割り当てと業務を割り当てを2段階に分けて解くより(無駄が少ない)良い答えが得られます.例:80人,30分単位の1ヶ月分のスケジュール作成で十数分で良い解が出ます.一般的な日単位や3シフト交代シフト最適化は問題規模や制約条件の厳しさにもよりますが,数秒〜数分程度で良い答えが出ます.

(最適化問題に共通する特徴ですが,規模が大きくても制約が緩いと速く良い解が見つかる場合があり,制約が厳しいと小規模問題でも良い解を見つけるのに時間がかかりますので,規模や計算時間はご参考程度にしてください.)

対応OS環境

  • Windows 64-bit
  • Mac OS 64-bit  
  • Linux (Ubuntu) 64-bit

対応OS環境は,適時,追加または修正される可能性があります.その他OSも状況に応じて提供可能な場合があります.詳細はお問い合わせください.

 

注意事項

「制約最適化ソルバーSCOPライセンス使用許諾契約書」 (2022年10月改訂版)

商品版と無料トライアル版共通です.

このソフトウェア使用許諾契約の条項を注意深くお読みください.
ソフトウェアをインストールし稼働できるようにすることで,お客様はこのソフトウェア使用許諾契約の条件に同意した ことになります.
ソフトウェア使用許諾契約の効力発生日は本件製品をインストールし,稼働できるようにした日です.

無料トライアル版ダウンロード

変数の数が15までの問題が求解できるトライアルバージョンを無料配布しております.

注)scop.pyを使用する場合,pythonの非標準モジュール(numpy,pandas,plotly)のインストールが必要です.これらの非標準モジュールはpipインストールで簡単に自動インストール可能です.

SCOP windows64トライアル版 (zip圧縮形式)ダウンロード   実行方法

SCOP mac64トライアル版(zip圧縮形式)ダウンロード      実行方法

SCOP Linuxトライアル版(zip圧縮形式)ダウンロード      実行方法

    

マニュアル

モデリングの詳細は,マニュアルならびに解説ビデオをご参照ください.

注)マニュアルにある[source]は一般公開してないため見れません.

    

インストール方法動画

 *** インストール方法 *** 

 *** 使用ガイド *** 

  

モデリング方法動画

◆ 1. SCOPによる制約最適化のモデリングと事例

◆ 2. SCOPとは,特徴とPythonインターフェース

◆ 3. 仕事割当問題

◆ 4. 仕事割当問題2

◆ 5. 生産割当問題

◆ 6. 投入順決定問題

◆ 7. 部屋割当問題

◆ 8. 人員割当問題

◆ 9. 初期解決定とまとめ

 もっと見る→

 

カスタマイズ

最適化ソルバーを用いたモデリング,システム開発など各種コンサルテイングやサポートが可能です.詳細はお問い合わせください.

コンサルティングサービス

分野別ソリューション