技術概要：PyCSP3-Scheduling

問題定義

PyCSP3 は、組み合わせ問題のモデル化と XCSP3 標準へのエクスポートを可能にする生産的な環境を提供する一方で、高レベルのスケジューリング抽象化に対するネイティブなサポートを欠いている。現在、モデル作成者はスケジューリング問題を低レベルの整数変数（開始時刻、処理時間）で符号化し、リソース競合に対する算術的な先行制約と排他論理和を手動で構築しなければならない。PyCSP3 は整数配列に対して NoOverlap や Cumulative などのグローバル制約を提供しているが、モデル作成者は開始時刻の配列、処理時間のリスト、リソースの高さなどを明示的に管理する必要がある。このアプローチは、本質的なスケジューリング構造を不明瞭にし、オプション性（発生するかどうかの不定性を持つタスク）やシーケンス依存のセットアップ時間のような機能の追加を複雑化し、新しいモデルに対して符号化をゼロから再構築することを要求する。既存の産業用ツール（CP Optimizer など）はスケジューリングオブジェクトを提供するが、しばしばモデルを特定の、場合によっては商用のソルバーに結合させており、一方、MiniZinc などのスタンドアロン言語にはファーストクラスの間隔変数型が存在しない。

手法

本論文は、PyCSP3 に専用のスケジューリング層を追加するライブラリ「PyCSP3-Scheduling」を導入する。中核的な手法は以下の通りである：

1. 抽象化層: このライブラリは、2 つの主要な変数型を導入する。
   • IntervalVar：開始、終了、サイズ（処理時間）、存在を表す属性を持つタスクを表す。固定、柔軟、オプション、有界、スケーリング（処理時間を強度プロファイルに結合）の 5 つの変種をサポートする。
   • SequenceVar：間隔変数のリストを順序付けられたシーケンスにグループ化し、通常は排他的リソース（例：機械）を表す。タイプ依存の遷移時間をサポートする。
2. コンパイル方式: このライブラリは新しいソルバーバックエンドを導入するのではなく、これらの高レベル抽象化を標準的な PyCSP3 変数と制約にコンパイルし、その後、標準的な XCSP3 インスタンスとしてエクスポートする。
   • 直接マッピング: パターンが既存のグローバル制約（遷移のない必須間隔など）と一致する場合、ライブラリは noOverlap や Cumulative などの標準的な XCSP3 グローバルを生成する。
   • 分解: 複雑なケース（存在ガード付きのオプション間隔やシーケンス依存のセットアップなど）の場合、ライブラリは抽象化をプリミティブな制約に分解する。例えば、現在の XCSP3 標準がグローバル制約におけるオプション間隔をサポートしていないため、オプション間隔を伴う SeqNoOverlap は、存在リテラルによってガードされた $O(n^2)$ のペアワイズ排他論理和にフォールバックする。
   • ハイブリッドモデリング: この層は PyCSP3 に埋め込まれており、モデル作成者が高レベルのスケジューリング構文と生の PyCSP3 制約を混合して使用できる（例：presence_of を使用してカスタム計数ロジックをトリガーする）。
3. 式システム: このライブラリは、start_of、end_of、presence_of などのアクセサを提供し、PyCSP3 式を返すことで、間隔属性に対して直接複雑な算術および論理結合を可能にする。

主要な貢献

本論文は、以下の 3 つの具体的な貢献を行う：

1. スケジューリング API: 間隔とシーケンスの抽象化を中心に据え、オプション性、強度関数、遷移を考慮したシーケンス化をサポートする、PyCSP3 向けの包括的な API。
2. コンパイル方式: これらの抽象化を、充足可能性と最適性を維持しつつ、ソルバーに依存しない PyCSP3/XCSP3 制約に低下させるメカニズム。
3. 実証評価: 17 のモデルファミリーにわたる 261 のペアインスタンス（古典的な PyCSP3 定式化対スケジューリング定式化）の厳密な比較。

結果

評価は、1200 秒のタイムアウト設定で ACE ソルバーを使用して 261 のペアインスタンスに対して行われた。主な知見は以下の通りである：

• 意味的整合性: 両方の定式化が最適性を証明した 72 のインスタンスにおいて、目的関数の値は完全に一致し（100%）、コンパイルが意味的な乖離を導入していないことを確認した。
• ソルバー状態の一致: 2 つの定式化は、ソルバーの状態（最適、充足、非充足、タイムアウト）について、ペアの 80.8% で一致した。不一致は主に、論理的誤りではなく、タイムアウトに関連する探索進捗の違いに起因していた。
• パフォーマンスのばらつき: 実行時間のパフォーマンスはファミリー間で大きく変動した：
  • 改善: 3 つのファミリーが明確な高速化を示した：MSPSP（5.82 倍）、AircraftLanding（3.47 倍）、Rehearsal（3.31 倍）。MSPSP の改善は、抽象化そのものではなく、PyCSP3 変数宣言における変数順序付けのアーティファクトに起因していた。一方、AircraftLanding と Rehearsal は、モデルサイズの縮小と構造のより良い捕捉によって恩恵を受けた。
  • 劣化: 3 つのファミリーが劣化した：LotSizing（0.29 倍）、MRCPSP（0.61 倍）、FlexibleJobshopScen（0.89 倍）。
    • MRCPSP の劣化は、オプション間隔のコンパイルがグローバルな noOverlap 制約の生成ではなく、ペアワイズ排他論理和にフォールバックすることに起因し、効率的な伝播を妨げていた。
    • LotSizing の劣化は、制約レベルの符号化の問題と、タイムアウト下での伝播の強さに関連していた。
    • FlexibleJobshopScen は、シナリオ全体にわたってオプションの決定を複製することによる、変数と制約の爆発的な増加という構造的な増大に苦しんだ。
• 構造的影響: 17 のファミリーのうち 8 つは、構造的な増大が negligible（<1% の変化）であった。他のファミリーでは、スケジューリング定式化はモデルサイズを縮小することもあり（例：BACP、Rehearsal）、時には著しく増加させることもあり（例：FlexibleJobshopScen で制約が +383.7%）、変動した。

意義と主張

本論文は、PyCSP3-Scheduling を、オプション性と遷移を考慮したシーケンス化を備えたファーストクラスの IntervalVar と SequenceVar 抽象化を提供し、かつソルバーに依存しない標準（XCSP3）にコンパイルする最初のスケジューリング層として位置づけている。

著者らは、このライブラリが PyCSP3 エコシステムの核となる原則であるモデリングとソルビングの完全な分離を維持することを強調している。これにより、モデルは修正なしに、ACE、Choco、CoSoCo、OR-Tools、CP Optimizer など、広範なソルバーエコシステムで使用可能となる。

本論文は、パフォーマンスに関する主張において控えめであり、実行時間の改善は普遍的ではなく、しばしば特定の問題構造やソルバーヒューリスティック（例：変数順序付け）に依存していると指摘している。著者らは、MSPSP における著しい高速化は、スケジューリング抽象化そのものではなく、変数宣言パターンに起因するアーティファクトである可能性が高いと明言している。主な価値提案は、コードの複雑さを削減し（例：フレキシブルジョブショップモデルでは行数が 31% 削減）、オプション性のような機能の追加を簡素化する、スケジューリング定式化の表現力と保守性にある。これは、特定のファミリーのパフォーマンスに影響を与えるコンパイルオーバーヘッドを時折引き起こす可能性があってもである。

今後の課題として、ペアワイズ分解を回避するためにオプション性サポートを備えた XCSP3 グローバル制約を生成するコンパイルの拡張と、外れ値ファミリーにおける構造的オーバーヘッドを削減するためのコンパイル規則の洗練が特定されている。