論文の概要: Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming

• arxiv url: http://arxiv.org/abs/2603.24033v1
• Date: Wed, 25 Mar 2026 07:48:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-26 21:06:11.18884
• Title: Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming
• Title（参考訳）: 混合整数線形計画のためのラグランジアン緩和スコアベース生成
• Authors: Ruobing Wang, Xin Li, Yujie Fang, Mingzhong Wang,
• Abstract要約: ラグランジュ緩和誘導微分方程式(SDE)に基づく生成的枠組み システムは、標準MILPソルバに対して、コンパクトで効果的な信頼領域サブプロブレムを集合的に定義する、多種多様な高品質なソリューション候補を生成する。
• 参考スコア（独自算出の注目度）: 13.20958452268089
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Predict-and-search (PaS) methods have shown promise for accelerating mixed-integer linear programming (MILP) solving. However, existing approaches typically assume variable independence and rely on deterministic single-point predictions, which limits solution diversityand often necessitates extensive downstream search for high-quality solutions. In this paper, we propose \textbf{SRG}, a generative framework based on Lagrangian relaxation-guided stochastic differential equations (SDEs), with theoretical guarantees on solution quality. SRG leverages convolutional kernels to capture inter-variable dependencies while integrating Lagrangian relaxation to guide the sampling process toward feasible and near-optimal regions. Rather than producing a single estimate, SRG generates diverse, high-quality solution candidates that collectively define compact and effective trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG consistently outperforms existing machine learning baselines in solution quality. Moreover, SRG demonstrates strong zero-shot transferability: on unseen cross-scale/problem instances, it achieves competitive optimality with state-of-the-art exact solvers while significantly reducing computational overhead through faster search and superior solution quality.
• Abstract（参考訳）: Predict-and-search(PaS)メソッドは、MILP(Mixed-integer linear programming)解決の高速化を約束している。 しかし、既存のアプローチは変分独立を前提としており、解の多様性を制限する決定論的単一点予測に依存している。 本稿では,ラグランジアン緩和誘導確率微分方程式(SDE)に基づく生成フレームワークである \textbf{SRG} を提案する。 SRGは畳み込みカーネルを活用して、変数間の依存関係をキャプチャし、ラグランジュ緩和を統合してサンプリングプロセスを実現可能な準最適領域へと導く。 SRGは単一の見積を生成するのではなく、標準MILPソルバのコンパクトかつ効果的な信頼領域サブプロブレムを集合的に定義する、多種多様な高品質なソリューション候補を生成する。 複数の公開ベンチマークを通じて、SRGはソリューションの品質において、既存の機械学習ベースラインを一貫して上回る。 さらに、SRGは強力なゼロショット転送可能性を示す: 目に見えないクロススケール/プロブレムのインスタンスでは、最先端の正確な解法と競合する最適性を達成し、高速な探索と優れた解品質によって計算オーバーヘッドを大幅に削減する。

関連論文リスト

• Applying a Random-Key Optimizer on Mixed Integer Programs [0.36700088931938835]
  Mixed-Integer Programs (MIP) は、幅広い意思決定アプリケーションで発生するNPハード最適化モデルである。 本稿では,MIPに対する高品質な解を計算するための,柔軟でメタヒューリスティックな代替手段として,RKO(Random-Key integer)フレームワークの利用について検討する。
  論文  参考訳（メタデータ） (2026-02-25T18:20:03Z)
• 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)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  本稿では,両者の時間的分離を必要とせずに,意思決定とIS分布を共同で更新する反復型アルゴリズムを提案する。 本手法は,IS分布系に対する目的的,軽度な仮定の凸性の下で,最小の変数分散を達成し,大域収束を保証する。
  論文  参考訳（メタデータ） (2025-04-04T16:10:18Z)
• Cascading CMA-ES Instances for Generating Input-diverse Solution Batches [1.932871350415445]
  ポストホックなユーザの好みに合わせて柔軟性を提供するため、高品質の多様なソリューションのバッチを目指すことが望ましい場合が多い。 本稿では,共分散行列適応進化戦略(CMA-ES)の並列実行をカスケード方式でタブ領域を継承する手法を提案する。 我々は,CMA-ES-Diversity Search (CMA-ES-DS)アルゴリズムが与えられた最小距離要件を尊重する高品質な解バッチを抽出できるトラジェクトリを生成することを実証的に実証した。
  論文  参考訳（メタデータ） (2025-02-19T13:55:51Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。