2025年10月21日火曜日

instance23/24の整数化課題

現状、 二つの課題があります。

１）AL1でコンパイル出来ない問題

２）整数化方法の高精度化

AL3は、下記Branch and Priceです。コパイに整数化方法について聞いてみました。



LP（線形計画）ソルバから整数化する方法には、以下のような代表的なアプローチがあります。これは、連続変数を含むLP問題を整数制約付きの問題（整数計画問題）に変換する際に用いられます。

🔧 LPソルバから整数化する主な方法

1. 分枝限定法（Branch and Bound）

  • LP緩和問題を解いて得られた非整数解をもとに、変数に整数制約を加えた部分問題を分割。
  • 各部分問題を再帰的に探索し、最適な整数解を見つける。
  • 商用ソルバ（Gurobi、CPLEX）や無料ソルバ（SCIP、CBC）で広く使われている。

2. 分枝価格法（Branch and Price）

  • 分枝限定法に列生成（Column Generation）を組み合わせた手法。
  • 特に大規模な整数計画問題（例：車両経路問題）に有効。

3. 分枝制約法（Branch and Cut）

  • 分枝限定法にカット制約（Cutting Planes）を加えて、探索空間を効率的に削減。
  • LP緩和解が整数解でない場合、制約を追加して非整数解を排除。

4. 切断平面法（Cutting Plane Method）

  • LP緩和問題を解いた後、非整数解を排除するための不等式（カット）を追加。
  • Gomoryカットなどが代表例。

5. ラグランジュ緩和法

  • 一部の制約を目的関数にペナルティ項として組み込み、緩和問題を解く。
  • 組合せ最適化問題に対して近似解を得る手法としても使われる。

6. ヒューリスティック・メタヒューリスティック

  • 厳密解ではなく、実用的な近似解を得るための手法。
  • 例：局所探索、遺伝的アルゴリズム、焼きなまし法など。

🧠 実装面でのポイント

  • Pythonでは PySCIPOpt や Python-MIP、PuLP などのライブラリを使って整数化が可能です。
  • モデル定義時に x = model.add_var(var_type=INTEGER) のように変数タイプを指定することで整数制約を加えられます。



コパイにFeasiblity　Pumpについて聞いてみました。



Feasibility Pump（実現可能性ポンプ）は、混合整数計画問題（MIP）において**実行可能な整数解を素早く見つけるための発見的手法（ヒューリスティック）**です。特に初期解の探索や整数化の補助として使われます。

🔍 Feasibility Pumpの概要

  • 目的：LP緩和で得られる非整数解をもとに、実行可能な整数解を見つける。

  • 手法の流れ：

    1. LP緩和問題を解いて連続解 ( x^* ) を得る。
    2. ( x^* ) の整数部分を丸めて整数ベクトル ( z ) を作成。
    3. ( z ) が制約を満たすかチェック。満たせば終了。
    4. 満たさない場合、目的関数を「( x ) と ( z ) の距離を最小化」に変更して再度LPを解く。
    5. 新しい ( x ) を得て再び丸める。
    6. このプロセスを繰り返すことで、実行可能な整数解に近づける。

  • 特徴：

    • 厳密解ではなく、実行可能な解を早期に得ることが目的。
    • 分枝限定法の初期解として使うと探索効率が向上する。
    • SCIPやCPLEXなどのソルバではオプションとして有効化可能。

⚙️ 実装・設定例（SCIPやNUOPT）

  • feasibility pump はソルバのオプションで設定可能：

    • Branch.FeasPump.ON：有効化
    • Branch.FeasPump.OFF：無効化
    • Branch.FeasPump.AUTO：自動判定

  • Pythonライブラリ（例：PySCIPOpt）でも setHeuristicParam などで制御可能。

🧠 応用と研究動向

  • 強化学習と組み合わせた「スマートFeasibility Pump」も研究されており、より効率的な初期解探索が可能になると期待されています。

必要であれば、Pythonでの実装例や他の発見的手法（RINS、Divingなど）との比較もできますよ。どんな場面で使いたいか教えていただければ、より実践的なアドバイスをお届けします。



コパイに聞いてみました。



Rounding heuristics（丸めヒューリスティクス）は、線形緩和（LP relaxation）で得られた非整数解を整数解に変換するための近似手法です。整数計画問題（特に0-1整数計画）において、厳密解の探索が困難な場合に、実行可能かつ「そこそこ良い」解を得るために使われます。

🔧 主なRounding Heuristicsの種類

1. 単純丸め（Simple Rounding）

  • 各変数を0.5以上なら1、未満なら0に丸める。
  • 制約違反が起こりやすく、実行可能性は保証されない。

2. 乱択丸め法（Randomized Rounding）

  • 線形緩和で得た値を確率とみなし、コイン投げで0または1に決定。
    • 例：( x_i = 0.8 ) → 80%の確率で1、20%で0
  • 実装がシンプルで、理論的にも良好な近似性能を持つ。
  • 集合被覆問題やスケジューリング問題などでよく使われる。

3. 独立丸め法（Independent Rounding）

  • 各変数を独立に乱択丸めする。
  • 制約を満たす保証はないが、期待値ベースで性能分析が可能。

4. 制約付き丸め（Constraint-aware Rounding）

  • 制約を満たすように丸め方を調整。
  • 例：丸め後に制約違反があれば、修正ステップを挿入。

5. ラグランジュ丸め（Lagrangian Rounding）

  • ラグランジュ緩和で得た双対情報を使って丸める。
  • より構造的な問題に適用される。

🧠 応用と実装例

  • Pythonでの実装は numpy.random.rand() を使って乱択丸めが可能。
  • 実務では「最適解は不要、実行可能な近似解で十分」という場面で活躍。
  • 例えばシフトスケジューリングや施設配置問題などで、短時間で良好な解を得る手段として有効です。

📚 参考資料



RINSについても聞きました。



RINS（Relaxation Induced Neighborhood Search）は、混合整数計画問題（MIP）に対する**発見的探索手法（ヒューリスティック）**の一つで、既存の解とLP緩和解の情報を活用して、局所探索を行うアルゴリズムです。特に、分枝限定法の探索を補助する目的で使われます。

🔍 RINSの基本アイデア

  • 目的：既存の実行可能な整数解を改善するために、探索空間の一部（近傍）を限定して再探索する。
  • 手法の流れ：
    1. 分枝限定法の途中で得られたLP緩和解と現在の最良整数解を比較。
    2. 両者で一致している変数を固定し、一致していない変数のみを探索対象とする。
    3. この限定された近傍で新たなMIPを解くことで、より良い解を得る可能性がある。

⚙️ 特徴と利点

  • 探索空間の縮小：一致している変数を固定することで、探索空間が大幅に減少。
  • 高速化：限定された近傍での探索なので、計算時間が短くなる。
  • 改善効果：初期解の改善や探索の加速に寄与する。
  • ソルバ対応：Gurobi、CPLEX、SCIPなどの主要ソルバでRINSが組み込まれている。

🧠 応用例

  • 大規模なスケジューリング問題や配置問題で、分枝限定法単体では収束が遅い場合に有効。
  • 他のヒューリスティック（Feasibility Pump、Divingなど）と組み合わせて使われることも多い。

📌 参考情報

  • NUOPTやSCIPのマニュアルでは、RINSを有効化するオプションが用意されています。
  • 例えば SCIP では heuristics/rins/freq や heuristics/rins/maxnodes などのパラメータで制御可能です。

RINSは「LP緩和解と整数解の差分に注目する」という点で、他のヒューリスティックとは一線を画しています。もし、具体的な問題に対してRINSを使いたい場合は、ソルバの設定やパラメータ調整のアドバイスもできますよ。

Sources: NTTデータ数理システム NUOPTマニュアル

Divingについても聞きました。

Diving（ダイビング）は、混合整数計画問題（MIP）におけるヒューリスティック手法の一種で、LP緩和解を出発点として、探索空間を深く潜っていくように局所探索を行うアルゴリズムです。特に、実行可能な整数解を素早く見つけるために使われます。

🧭 Divingの基本的な流れ

  1. LP緩和問題を解く
    線形計画の連続解（非整数解）を取得。

  2. 丸めや固定を行う
    LP解の中で「確信度の高い」変数を整数に固定。たとえば、0.99なら1に、0.01なら0に。

  3. 部分問題を解く
    固定された変数をもとに、残りの変数でLPを再解き、さらに丸める。

  4. 探索を継続
    実行可能な整数解が得られるまで、または制限時間・ノード数に達するまで繰り返す。

🔍 Divingのバリエーション

  • Fractional Diving：LP解で最も非整数度が高い変数から順に固定。
  • Objective Diving：目的関数の改善に寄与する変数を優先して固定。
  • Pseudo-cost Diving：過去の探索履歴から、分枝効果が高い変数を選ぶ。
  • Strong Diving：複数の候補を試して最も良い分枝を選ぶ（計算コスト高）。

⚙️ Divingの特徴と利点

  • 高速性：厳密な探索よりも高速に実行可能解を得られる。
  • 初期解生成：分枝限定法の初期解として有効。
  • ソルバ対応：SCIPやCPLEXなどでDivingヒューリスティックが組み込まれている。

📌 実装例（SCIP）

SCIPでは以下のようなパラメータで制御可能です：

  • heuristics/diving/freq：Divingの頻度
  • heuristics/diving/maxdepth：探索の最大深さ
  • heuristics/diving/strategy：使用するDiving戦略（fractional, objectiveなど）

Divingは「深く潜っていく」イメージ通り、探索空間の奥にある実行可能解を狙う手法です。Feasibility PumpやRINSと組み合わせることで、より強力な初期解探索が可能になります。

Sources: 東京大学 最適化アルゴリズムの基礎東北大学 情報システム評価学講義資料Wikipedia 整数計画問題





現状AL3で使用してヒューリスティクスは、AL1(MaxSAT)とRounding　Heuristicsを組み合わせたものです。この方法は、特にRosterにソフト制約がないことが特徴のベンチマーク（ScheudlingBenchmarks）で、極めて有効であることが分かっています。

New Scehduling Benchmarks

しかし、課題もあります。Rounding　Heuristicsでは、１.0を確率１、つまり正しい値として固定化（ハード制約化）してしまいます。実は、この変換がいつも正しい、という訳ではありません。実際Instance13/20で、ROOTにおけるLP値は、次のような分布になっていました。


これは、UBが得られたときのシフトを1として、それに対するROOTノードにおけるLP値を正規化したHistogramです。例えば、instance20における1の値が最もあり得ることを示していて、50%近くが正しい変換であることを示しています。0の割合が4%位で、完全に間違っている割合を示しています。これに対してinstance13の正解率は、3割程度で、間違っているのも15％位あることが分かります。このことから、instance13の方が深くDepthを稼がないと正解に近い値に辿り着けない、難易度が高い問題、と言うことが言えます。

この値は、ROOTでの値なので、Branchingを行っていけば、急速に正解率を上げることが出来ます。LPソルバが高速ならば、下手にヒューリスティクスを駆使するよりもDepthを深くした方が、早く真値UBを得ることが出来ます。

問題は、instance23/24のような大規模問題では、LPソルバが、とんでもなく遅いので、ヒューリスティクスに工夫を加えて、浅いDepthでも早期にUBを得る必要がある、ということです。つまり、

■単純なRounding　Heuristicsよりも信頼度の高い方法で、

■大規模問題もコンパイルできる＝（１）課題

方法を編み出すことが課題となります。この要件から、Rins,Diving,Feasiblity Pumpといった既存方法ではなく、新しい方法が必要とされています。

Lpソルバの方は、ほぼ最高性能のソルバを使うことが出来ます。RosteringGraphも予備データの収集が完了し目途がたちました。できる努力は、上記のみということになります。

投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)