Feasibility Polishingについて聞いてみました

 CUPDLPXのソースを見ていて見慣れない実装があったのでCopilotに聞いてみました。AIから逆に質問されることもあるのですね。

要点:
cuPDLPXにおける feasibility polishing とは、一次法（first-order method）で得られた近似解を、追加の処理で「実行可能性（feasibility）」を改善する技術です。大規模LPを高速に解く際、反復法が生成する解は制約を完全には満たさないことが多いため、それを「磨き上げる」工程が導入されています。

---

🔍 背景

• cuPDLPX は GPU 上で動作する線形計画法 (LP) ソルバで、Restarted Halpern PDHG（Primal-Dual Hybrid Gradient の改良版）をベースにしています。
• 一次法はスケーラブルで高速ですが、解の精度や制約の満足度が十分でない場合があります。そこで「feasibility polishing」が役立ちます。

✨ Feasibility Polishing の役割

• 目的:
  • 制約違反を減らし、より「実行可能」な解を得る。
  • 特に大規模LPで、近似解を実用的な水準に引き上げる。
• 方法:
  • 一次法で得られた解を初期点として、追加の補正ステップを行う。
  • Google OR-Tools の PDLP 実装でも v9.7 以降で導入されており、cuPDLPX も同様の機能を取り込んでいます。
• 効果:
  • 実行可能性を改善することで、LP緩和やベンチマークでの精度が向上。
  • 特に「高精度」「プレソルブ可能」な設定で顕著な改善が報告されています。

📌 まとめ

• Feasibility polishing = 一次法で得た近似解を制約により適合させる後処理。
• cuPDLPXでは、GPU最適化されたPDHG法に加え、この polishing を組み込むことで、大規模LPに対して高速かつ高精度な解を提供できるようになっています。

---

Sources:

---

孝幸さんは LPソルバの実装やヒューリスティクスに詳しいので、ここで質問です。
Feasibility polishing は「解の実行可能性を改善する後処理」ですが、実務上は 精度を優先するか、速度を優先するかで使い方が変わります。孝幸さんなら、GPUベースの cuPDLPX を使う際に polishing を「常時オン」にしますか？それとも「必要なときだけオン」にしますか？

なるほど、非常に理にかなった運用ですね 👍。

一次法ベースの cuPDLPX では、feasibility polishing は「解をきれいに制約に合わせる」ための後処理ですが、常時オンにすると計算コストが増えてしまいます。孝幸さんのように 整数解を扱う場面や、CROSSOVER（単体法やバリア法への橋渡し）を行う場面でだけ polishing を使うのは合理的です。

• 整数解をミスしたくないとき
  → LP 緩和の解が制約違反を含んでいると、整数化の際に誤った分枝やカットが導入される可能性があります。polishing によって制約を満たした解を渡すことで、MIP ソルバの信頼性が上がります。

• Crossover が必要なとき
  → 一次法の近似解を単体法に渡す場合、制約違反があると初期基底が不安定になります。polishing を挟むことで、より「きれいな」基底を得られ、Crossover の成功率や速度が改善されます。

つまり、速度優先なら polishing はオフ、精度や後続処理の安定性を優先するならオンという切り替えが最適ですね。

---

💡 孝幸さんのように MIP や Crossover を意識している方にとっては、polishing を「必要なときだけオン」にする方針がベストプラクティスだと思います。