論文の概要: Scalable Mixed-Integer Optimization with Neural Constraints via Dual Decomposition

• arxiv url: http://arxiv.org/abs/2511.09186v1
• Date: Thu, 13 Nov 2025 01:38:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-13 22:34:54.454035
• Title: Scalable Mixed-Integer Optimization with Neural Constraints via Dual Decomposition
• Title（参考訳）: 双対分解によるニューラル制約を用いたスケーラブル混合整数最適化
• Authors: Shuli Zeng, Sijia Zhang, Feng Wu, Shaojie Tang, Xiang-Yang Li,
• Abstract要約: 本稿では,拡張ラグランジュ乗算器による単一結合等式 u=x を緩和し,問題をバニラ MIP と制約付き NN ブロックに分割する,新しい双対分解フレームワークを提案する。 各部分は、MIPサブプロブレムの最適分岐とカットに適合する解法によって取り組まれ、NNサブプロブレムの1次最適化はモジュラーのままであり、各イテレーションコストはNNサイズと直線的にのみスケールする。
• 参考スコア（独自算出の注目度）: 36.178612385818305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Embedding deep neural networks (NNs) into mixed-integer programs (MIPs) is attractive for decision making with learned constraints, yet state-of-the-art monolithic linearisations blow up in size and quickly become intractable. In this paper, we introduce a novel dual-decomposition framework that relaxes the single coupling equality u=x with an augmented Lagrange multiplier and splits the problem into a vanilla MIP and a constrained NN block. Each part is tackled by the solver that suits it best-branch and cut for the MIP subproblem, first-order optimisation for the NN subproblem-so the model remains modular, the number of integer variables never grows with network depth, and the per-iteration cost scales only linearly with the NN size. On the public \textsc{SurrogateLIB} benchmark, our method proves \textbf{scalable}, \textbf{modular}, and \textbf{adaptable}: it runs \(120\times\) faster than an exact Big-M formulation on the largest test case; the NN sub-solver can be swapped from a log-barrier interior step to a projected-gradient routine with no code changes and identical objective value; and swapping the MLP for an LSTM backbone still completes the full optimisation in 47s without any bespoke adaptation.
• Abstract（参考訳）: 深層ニューラルネットワーク(NN)を混合整数プログラム(MIP)に組み込むことは、学習した制約で意思決定を行う上で魅力的な方法だが、最先端のモノリシックな線形化は、サイズが爆発的に大きくなり、すぐに難解になる。 本稿では,拡張ラグランジュ乗算器による単一結合等式 u=x を緩和し,問題をバニラ MIP と制約付き NN ブロックに分割する,新しい双対分解フレームワークを提案する。 NNサブプロブレムの1次最適化はモジュラーのままであり、整数変数の数はネットワークの深さとともに決して増加しない。 公開 \textsc{SurrogateLIB} ベンチマークでは、我々のメソッドは \textbf{scalable}, \textbf{modular}, \textbf{adaptable} を証明している: 最大のテストケースでは、正確な Big-M 式よりも高速に実行される。

関連論文リスト

• Fixed-Point RNNs: Interpolating from Diagonal to Dense [18.06917701940596]
  リニアリカレントニューラルネットワーク(RNN)とステートスペースモデル(SSM)は、トランスフォーマーアーキテクチャにおけるシーケンス混合層としてのソフトマックスアテンションに代わる有望な代替手段となっている。 しかし、現在のモデルはチャネルワイド(対角)配列の混合に依存するため、RNNの完全な状態追跡表現性は示さない。 本稿では, 並列化可能な対角RNNの固定点としての高密度線形RNNのパラメータ化について検討する。
  論文  参考訳（メタデータ） (2025-03-13T18:50:22Z)
• Training Deep Learning Models with Norm-Constrained LMOs [56.00317694850397]
  線形最小化オラクル(LMO)を用いて問題の幾何学に適応する新しいアルゴリズム群を提案する。 我々は,Adamに頼らずに,我々のアルゴリズムであるScionを用いたナノGPTトレーニングの大幅な高速化を示す。
  論文  参考訳（メタデータ） (2025-02-11T13:10:34Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
  混合整数プログラミング(MIP)技術は最適化問題の定式化と解法を提供する。 MIP-GNNは、データ駆動の洞察でそのような問題を解決するための一般的なフレームワークである。 MIP-GNNを最先端のMIP解決器に統合し,ノード選択やウォームスタートといったタスクに適用する。
  論文  参考訳（メタデータ） (2022-05-27T19:34:14Z)
• Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networks [0.07614628596146598]
  二元活性化関数と連続または整数重み付きディープニューラルネットワーク(BDNN)について検討する。 BDNNは、古典的な混合整数計画解法により、大域的最適性に解けるような、有界な重み付き混合整数線形プログラムとして再構成可能であることを示す。 トレーニング中にBDNNの堅牢性を強制するロバストモデルが初めて提示される。
  論文  参考訳（メタデータ） (2021-10-21T18:02:58Z)
• Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization [8.386501595252]
  BMM(Block Majorization-minimativeization)は、制約付き非負のサロゲートに対する単純な反復アルゴリズムである。 BMMは,様々なアルゴリズムに対して,新しい一階最適度尺度を生成する。 また, BMM の収束率を向上させるために, 減衰半径の付加的利用が有効であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T07:53:09Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)

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

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