論文の概要: Solving Integer Linear Programming with Parallel Tempering
- arxiv url: http://arxiv.org/abs/2605.29366v1
- Date: Thu, 28 May 2026 05:09:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-30 02:45:55.749359
- Title: Solving Integer Linear Programming with Parallel Tempering
- Title（参考訳）: 並列テンパリングによる整数線形プログラミングの解法
- Authors: Kyuil Sim, Sanghyeok Choi, Jinkyoo Park,
- Abstract要約: 線形プログラミング(ILP)は、幅広い最適化問題をモデリングするための汎用的なフレームワークとして機能する。
我々は、トレーニングや外部のソルバを使わずに、個別の実行可能な領域を直接探索する、ICPのためのソルバフリーサンプリングベース最適化フレームワークを提案する。
提案手法は,200秒の予算内での4つのタスクのうち2つのタスクにおいて,Gurobiに適合あるいは超越した4つのベンチマークでSCIPを一貫して上回り,学習ベースの手法よりも分散シフトに対してかなり頑健である。
- 参考スコア（独自算出の注目度）: 25.230514748331274
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Integer Linear Programming (ILP) serves as a versatile framework for modeling a wide range of combinatorial optimization problems, typically addressed by sophisticated exact solvers or heuristics. While learning-based approaches have recently shown their effectiveness, they suffer from poor generalization to out-of-distribution instances and inherent dependence on external solvers. In this work, we propose a solver-free, sampling-based optimization framework for ILP that directly explores discrete feasible regions without training or external solvers. Exploiting the linear structure of ILP, we employ a Locally-Balanced Proposal to construct a transition kernel, thereby avoiding the gradient approximation. To overcome the highly multimodal nature of ILP energy landscapes, we integrate Parallel Tempering. In addition to standard temperature tempering, we introduce penalty tempering, which modulates constraint barriers while preserving the objective landscape over feasible solutions. Empirically, our method consistently outperforms SCIP across all four benchmarks, matches or exceeds Gurobi on two of four tasks within a 200-second budget, and is substantially more robust to distribution shift than learning-based methods. Furthermore, on MIPLIB 2017 instances, our framework remains competitive with classical solvers without any problem-specific tuning.
- Abstract（参考訳）: Integer Linear Programming (ILP) は、様々な組合せ最適化問題をモデリングするための汎用的なフレームワークとして機能する。
学習に基づくアプローチは、最近、その効果を示したが、それらは、分布外インスタンスへの一般化の欠如と、外部の解法に固有の依存に悩まされている。
そこで本研究では,ICP をトレーニングや外部のソルバを使わずに個別実現可能な領域を直接探索する,解法自由サンプリングに基づく ILP 最適化フレームワークを提案する。
ILPの線形構造をエクスプロートし、ローカルベース提案を用いて遷移カーネルを構築し、勾配近似を回避する。
ILPエネルギーランドスケープのマルチモーダルな性質を克服するため、並列テンパリングを統合する。
標準的な温度テンパリングに加えて,制約バリアを変調するペナルティテンパリングも導入する。
提案手法は,200秒の予算内での4つのタスクのうち2つをグロビに一致させたり,超えたりすることで,SCIPを一貫して上回り,学習ベースの手法よりも分散シフトに対してかなり堅牢である。
さらに,MIPLIB 2017インスタンスでは,問題固有のチューニングを伴わずに,従来の解法と競合するフレームワークが引き続き存在する。
関連論文リスト
- Learning to Solve Orienteering Problem with Time Windows and Variable Profits [5.973834170744548]
時間ウィンドウと可変利益(OPTWVP)によるオリエンテーリング問題は、多くの実世界のアプリケーションで一般的である。
サービス時間誘導軌道(DeCoST)を用いた学習型2段階Decoupled離散連続最適化を提案する。
OPTWVPインスタンスの実験では、DeCoSTは最先端のコンストラクティブソルバと最新のメタヒューリスティックアルゴリズムの両方より優れていることが示されている。
論文 参考訳（メタデータ） (2026-03-06T13:24:10Z) - Parallel Diffusion Solver via Residual Dirichlet Policy Optimization [88.7827307535107]
拡散モデル(DM)は、最先端の生成性能を達成したが、シーケンシャルなデノナイジング特性のため、高いサンプリング遅延に悩まされている。
既存のソルバベースの加速度法では、低次元の予算で画像品質が著しく低下することが多い。
本研究では,各ステップに複数の勾配並列評価を組み込んだ新しいODE解法であるEnsemble Parallel Directionsolvr(EPD-EPr)を提案する。
論文 参考訳（メタデータ） (2025-12-28T05:48:55Z) - GaussianPSL: A novel framework based on Gaussian Splatting for exploring the Pareto frontier in multi-criteria optimization [1.325953054381901]
本稿では,多目的最適化を用いた非目的多様性学習のための新しいアプローチを提案する。
本手法は各領域の局所的特徴を統合し,新たなアグリゲータフレームワークによって統合する。
実験の結果,本手法は非目的多様性学習において標準PSLモデルよりも優れていた。
この作業は、挑戦的な現実世界のベンチマークの下で、効果的でスケーラブルな新たな方向性を提供する。
論文 参考訳（メタデータ） (2025-09-22T15:21:22Z) - Large Language Models as End-to-end Combinatorial Optimization Solvers [45.32050615257007]
物流や製造などの意思決定シナリオの中心となる組合せ最適化(CO)問題は、伝統的に問題固有のアルゴリズムを使用して解決される。
既存のアプローチは、コード生成やソルバ呼び出しといった中間ステップに依存しており、その汎用性とアクセシビリティを制限している。
本稿では,大規模言語モデル(LLM)を,自然言語問題記述をソリューションに直接マッピングすることで,エンドツーエンドのCOソルバとして機能させる,新たなフレームワークを提案する。
論文 参考訳（メタデータ） (2025-09-21T01:30:30Z) - FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming [52.52020895303244]
Mixed-Integer Linear Programming (MILP)は、複雑な意思決定問題の基本的なツールである。
混合整数線形計画法(FMIP)のための連立連続整数フローを提案する。これはMILPソリューションにおける整数変数と連続変数の共分散をモデル化する最初の生成フレームワークである。
FMIPは任意のバックボーンネットワークや様々なダウンストリームソルバと完全に互換性があり、現実世界のMILPアプリケーションにも適している。
論文 参考訳（メタデータ） (2025-07-31T10:03:30Z) - Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。
数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文 参考訳（メタデータ） (2024-09-02T12:55:27Z) - Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。
我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。
車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
論文 参考訳（メタデータ） (2024-07-24T12:00:30Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。