制約の最適化

制約最適化、または制約プログラミング（CP）は、非常に大規模な候補セットから実行可能な解決策を特定するときに付けられた名前です。任意の制約に関して問題をモデル化できます。CP の問題は、多くの科学技術分野において発生します。（かつて「コンピュータ」が「計算を行う人」を意味するのと同様に、「プログラミング」という言葉は多少の誤解です。ここでの「プログラミング」は、コンピュータ言語でプログラミングするのではなく、計画を構成することを指します）。

CP は、最適化（最適なソリューションを見つける）ではなく実現可能性（実現可能なソリューションを見つけること）に基づいており、目的関数ではなく制約と変数に重点を置きます。実際、CP の問題には目的関数さえない場合があります。目標は、問題に制約を追加して、考えられる非常に多くの解決策をより管理しやすいサブセットに絞り込むことです。

CP に適した問題の例として、従業員のスケジューリングが挙げられます。 この問題は、工場など、継続的に運営する企業が従業員の週単位スケジュールを作成する必要がある場合に発生します。簡単な例を挙げます。1 日に 8 時間のシフトを 3 回行い、4 人中 3 人の従業員を毎日異なるシフトに割り当て、4 日目を休日します。このような小規模なケースでも、可能なスケジュール数は膨大で、1 日に 4! = 4 * 3 * 2 * 1 = 24 件の従業員割り当てが可能であるため、1 週間のスケジュールは 244.5 を上回ります。通常、実現可能なソリューションの数を減らす他の制約があります。たとえば、各従業員が少なくとも週に最低何日勤務するのかなどです。CP メソッドは、新しい制約を追加しても実行可能なソリューションを追跡するため、現実世界の大規模なスケジューリング問題を解決するための強力なツールとなります。

CP は、世界中に広範で活発なコミュニティを擁しており、専門の科学雑誌、学会、さまざまな解決技術の兵器などが存在します。CP は、計画やスケジューリングなど、異種混合の制約を伴うさまざまなドメインで成功しています。

ツール

Google では、CP に関する問題を解決する複数の方法を提供しています。

  • CP-SAT ソルバー: SAT（充足可能性）方法を使用する制約プログラミング ソルバー。
  • 元の CP ソルバー: ルーティング ライブラリで使用される制約プログラミング ソルバー。

線形目的と線形制約で問題をモデル化できる場合、線形計画問題であるため、MPSolver の使用を検討してください。（ただし、ルートの問題は通常、線形モデルで表現できる場合でも、車両ルーティング ライブラリで最適に解決されます）。

例

次のセクションでは、制約プログラミングの主要な OR-Tools ソルバーである CP-SAT ソルバーについて説明します。（SAT は充足可能性の略です。解法では、CP メソッドとともに SAT 問題を解決するための手法が使用されます）。

CP-SAT ソルバーに適したスケジューリング問題の例を次に示します。

典型的な CP の問題は、N クイーン問題と暗号パズルです。