商用ソルバー

本書では,以下の商用ソルバーを利用している.

  • 数理最適化ソルバー Gurobi
  • 制約最適化ソルバー SCOP
  • スケジューリング最適化ソルバー OptSeq
  • 配送最適化ソルバー METRO
  • ロジスティクス・ネットワーク設計システム MELOS
  • シフト最適化システム OptShift
  • 集合被覆最適化ソルバー OptCover
  • 一般化割当最適化ソルバー OptGAP
  • パッキング最適化ソルバー OptPack
  • 巡回セールスマン最適化ソルバー CONCORDE, LKH

Gurobi

数理最適化ソルバー Gurobi は,https://www.gurobi.com/ からダウンロード・インストールできる.アカデミックは無料であり,インストール後1年間使用することができる. 日本における総代理店は,オクトーバースカイ社 https://www.octobersky.jp/ である.

Gurobiで対象とするのは,数理最適化問題である.数理最適化とは,実際の問題を数式として書き下すことを経由して, 最適解,もしくはそれに近い解を得るための方法論である. 通常,数式は1つの目的関数と幾つかの満たすべき条件を記述した制約式から構成される.

目的関数とは,対象とする問題の総費用や総利益などを表す数式であり, 総費用のように小さい方が嬉しい場合には最小化,総利益のように大きい方が嬉しい場合には最大化を目的とする. 問題の本質は最小化でも最大化でも同じである. (最大化は目的関数にマイナスの符号をつければ最小化になる.)

Gurobiの文法の詳細については,拙著「あたらしい数理最適化-Python言語とGurobiで解く-」(近代科学社)を参照されたい.

オープンソースの数理最適化ソルバーもある.本書では,Gurobiと同様の文法で記述できるmypulp(オープンソースのPuLPのラッパーモジュール)を用いている.

mypulpやその他のオープンソースライブラリの詳細については,拙著「Python言語によるビジネスアナリティクス-実務家のための最適化・統計解析・機械学習」(近代科学社)を参照されたい.

SCOP

SCOP(Solver forCOnstraint Programing:スコープ)は, 大規模な制約最適化問題を高速に解くためのソルバーである.

ここで,制約最適化(constraint optimization) 数理最適化を補完する最適化理論の体系であり, 組合せ最適化問題に特化した求解原理-メタヒューリスティクス(metaheuristics)-を用いるため, 数理最適化ソルバーでは求解が困難な大規模な問題に対しても,効率的に良好な解を探索することができる.

このモジュールは, すべてPythonで書かれたクラスで構成されている. SCOPのトライアルバージョンは, http://logopt.com/scop2/ からダウンロード,もしくはgithub https://github.com/mikiokubo/scoptrial からクローンできる. また,テクニカルドキュメントは,https://scmopt.github.io/manual/14scop.html にある.

SCOPで対象とするのは,汎用の重み付き制約充足問題である.

一般に制約充足問題(constraint satisfaction problem)は,以下の3つの要素から構成される.

  • 変数(variable): 分からないもの,最適化によって決めるもの. 制約充足問題では,変数は,与えられた集合(以下で述べる「領域」)から1つの要素を選択することによって決められる.

  • 領域(domain): 変数ごとに決められた変数の取り得る値の集合.

  • 制約(constraint): 幾つかの変数が同時にとることのできる値に制限を付加するための条件. SCOPでは線形制約(線形式の等式,不等式),2次制約(一般の2次式の等式,不等式), 相異制約(集合に含まれる変数がすべて異なることを表す制約)が定義できる.

制約充足問題は,制約をできるだけ満たすように, 変数に領域の中の1つの値を割り当てることを目的とした問題である.

SCOPでは,重み付き制約充足問題(weighted constraint satisfaction problem) を対象とする.

ここで「制約の重み」とは,制約の重要度を表す数値であり, SCOPでは正数値もしくは無限大を表す文字列 'inf'を入力する. 'inf'を入力した場合には,制約は絶対制約(hard constraint)とよばれ, その逸脱量は優先して最小化される. 重みに正数値を入力した場合には,制約は考慮制約(soft constraint)とよばれ, 制約を逸脱した量に重みを乗じたものの和の合計を最小化する.

すべての変数に領域内の値を割り当てたものを(solution)とよぶ. SCOPでは,単に制約を満たす解を求めるだけでなく, 制約からの逸脱量の重み付き和(ペナルティ)を最小にする解を探索する.

SCOPモジュールの基本クラス

SCOPは,以下のクラスから構成されている.

  • モデルクラス Model
  • 変数クラス Variable
  • 制約クラス Constraint (これは,以下のクラスのスーパークラスである.)

    • 線形制約クラス Linear
    • 2次制約クラス Quadratic
    • 相異制約クラス Alldiff

OptSeq

スケジューリング(scheduling)とは,稀少資源を諸活動へ(時間軸を考慮して)割り振るための方法に対する理論体系である. スケジューリングの応用は,工場内での生産計画,計算機におけるジョブのコントロール,プロジェクトの遂行手順の決定など,様々である.

ここで考えるのは,以下の一般化資源制約付きスケジューリングモデルであり,ほとんどの実際問題をモデル化できるように設計されている.

  • 複数の作業モードをもつ作業
  • 時刻依存の資源使用可能量上限
  • 作業ごとの納期と重み付き納期遅れ和
  • 作業の後詰め
  • 作業間に定義される一般化された時間制約
  • モードごとに定義された時刻依存の資源使用量
  • モードの並列処理
  • モードの分割処理
  • 状態の考慮

OptSeq(オプトシーク)は,一般化スケジューリング問題に対する最適化ソルバーである. スケジューリング問題は,通常の混合整数最適化ソルバーが苦手とするタイプの問題であり, 実務における複雑な条件が付加されたスケジューリング問題に対しては,専用の解法が必要となる. OptSeqは,スケジューリング問題に特化したメタヒューリスティクス(metaheuristics)を用いることによって, 大規模な問題に対しても短時間で良好な解を探索することができるように設計されている

このモジュールは, すべてPythonで書かれたクラスで構成されている. OptSeqのトライアルバージョンは, http://logopt.com/optseq/ からダウンロード,もしくは github https://github.com/mikiokubo/optseqtrial からクローンできる. また,テクニカルドキュメントは,https://scmopt.github.io/manual/07optseq.html にある.

OptSeqモジュールの基本クラス

行うべき仕事(ジョブ,作業,タスク)を作業(activity;活動)とよぶ. スケジューリング問題の目的は作業をどのようにして時間軸上に並べて遂行するかを決めることであるが, ここで対象とする問題では作業を処理するための方法が何通りかあって,そのうち1つを選択することによって 処理するものとする.このような作業の処理方法をモード(mode)とよぶ.

納期や納期遅れのペナルティ(重み)は作業ごとに定めるが, 作業時間や資源の使用量はモードごとに決めることができる.

作業を遂行するためには資源(resource)を必要とする場合がある. 資源の使用可能量は時刻ごとに変化しても良いものとする. また,モードごとに定める資源の使用量も作業開始からの経過時間によって変化しても良いものとする. 通常,資源は作業完了後には再び使用可能になるものと仮定するが, お金や原材料のように一度使用するとなくなってしまうものも考えられる. そのような資源を再生不能資源(nonrenewable resource)とよぶ.

作業間に定義される時間制約(time constraint)は, ある作業(先行作業)の処理が終了するまで,別の作業(後続作業)の処理が開始できないことを表す 先行制約を一般化したものであり, 先行作業の開始(完了)時刻と後続作業の開始(完了)時刻の 間に以下の制約があることを規定する

先行作業の開始(完了)時刻 $+$ 時間ずれ $\leq$ 後続作業の開始(完了)時刻

ここで,時間ずれは任意の整数値であり負の値も許すものとする. この制約によって,作業の同時開始,最早開始時刻,時間枠などの様々な条件を記述することができる.

OptSeqでは,モードを作業時間分の小作業の列と考え,処理の途中中断や並列実行も可能であるとする.その際,中断中の資源使用量や並列作業中の資源使用量も別途定義できるものとする.

また,時刻によって変化させることができる状態(state)が準備され,モード開始の状態の制限やモードによる状態の推移を定義できる.

METRO

METRO (MEta Truck Routing Optimizer)は,配送計画問題に特化したソルバーである. METROでは,ほとんどの実際問題を解けるようにするために,以下の一般化をした配送計画モデルを考える.

  • 複数時間枠制約
  • 多次元容量非等質運搬車
  • 配達・集荷
  • 積み込み・積み降ろし
  • 複数休憩条件
  • スキル条件
  • 優先度付き
  • パス型許容
  • 複数デポ(運搬車ごとの発地,着地)

SCMOPTプロジェクトの一部としてデモが https://www.logopt.com/demo/ にあり,概要は https://www.logopt.com/metro/ にある. また,テクニカルドキュメントは,https://scmopt.github.io/manual/02metro.html にある.

MELOS

MELOS (MEta Logistics Optimization System)は,ロジスティクス・ネットワーク設計問題に対する最適化システムである.

SCMOPTプロジェクトの一部としてデモが https://www.logopt.com/demo/ にあり,概要は https://www.logopt.com/melos/ にある. また,テクニカルドキュメントは,https://scmopt.github.io/manual/05lnd.html にある.

MESSA

MESSA (MEta Safety Stock Allocation system)は,在庫計画問題に対する最適化システムである.

SCMOPTプロジェクトの一部としてデモが https://www.logopt.com/demo/ にあり,概要は https://www.logopt.com/messa/ にある. また,テクニカルドキュメントは,https://scmopt.github.io/manual/03inventory.html にある.

OptLot

OptLotは,動的ロットサイズ決定問題に対する最適化システムである.

SCMOPTプロジェクトの一部としてデモが https://www.logopt.com/demo/ にあり,概要は https://www.logopt.com/optlot/ にある. また,テクニカルドキュメントは,https://scmopt.github.io/manual/11lotsize.html にある

OptShift

OptShiftは,シフト計画問題に対する最適化システムである.

SCMOPTプロジェクトの一部としてデモが https://www.logopt.com/demo/ にある. また,テクニカルドキュメントは,https://scmopt.github.io/manual/10shift.html にある

OptCover

OptCoverは,大規模な集合被覆問題を高速に解くためのソルバーである. アカデミック利用は無料であり,作者に直接連絡をとることによって利用可能である.作者のHPを以下に示す.

http://www.co.mi.i.nagoya-u.ac.jp/~yagiura/

商用の場合には以下のサイトを参照されたい.

https://www.logopt.com/optcover/

OptGAP

OptCoverは,大規模な一般化割当問題を高速に解くためのソルバーである. アカデミック利用は無料であり,作者に直接連絡をとることによって利用可能である.作者のHPを以下に示す.

http://www.co.mi.i.nagoya-u.ac.jp/~yagiura/

商用の場合には以下のコンタクトフォームを使用されたい.

https://www.logopt.com/contact-us/#contact

OptPack

OptPackは,大規模な2次元パッキング問題を高速に解くためのソルバーである. アカデミック利用は無料であり,作者に直接連絡をとることによって利用可能である.作者のHPを以下に示す.

https://sites.google.com/g.chuo-u.ac.jp/imahori/

商用の場合には以下のコンタクトフォームを使用されたい.

https://www.logopt.com/contact-us/#contact

CONCORDE

CONCORDEは,巡回セールスマン問題に対する厳密解法と近似解法であり,以下のサイトからダウンロードできる.

https://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm

アカデミック利用は無料であるが,商用利用の場合には作者のWilliam Cookに連絡をする必要がある.

LKH

LKHは,巡回セールスマン問題に対する近似解法(HelsgaunによるLin-Kernighan法)であり,以下のサイトからダウンロードできる.

http://webhotel4.ruc.dk/~keld/research/LKH-3/

アカデミック・非商用のみ無料であるが,商用利用の場合には作者のKeld Helsgaunに連絡をする必要がある.