Coonstraint Programming Solver SCOP

ドキュメント

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

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

このモジュールは, すべてPythonで書かれたクラスで構成されている. SCOPのトライアルバージョンは, http://logopt.com/scop2/ からダウンロード,もしくはgithub https://github.com/mikiokubo/scoptrial からクローンできる.

重み付き制約充足問題

ここでは,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