論文の概要: Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing

• arxiv url: http://arxiv.org/abs/2207.02087v1
• Date: Tue, 5 Jul 2022 14:46:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-06 15:50:08.648028
• Title: Learning to Accelerate Approximate Methods for Solving Integer Programming via Early Fixing
• Title（参考訳）: 初期修正による整数計画の近似解法を高速化する学習
• Authors: Longkang Li, Baoyuan Wu
• Abstract要約: いくつかの反復近似法によって解かれた変数は、非常に長い反復で最終的な収束した離散状態の周りに変動する。 この観測から着想を得た我々は、これらの変動変数を収束状態に早期に固定することにより、これらの近似手法を加速することを目指している。 初期固定プロセス全体をマルコフ決定プロセスとして定式化し、模倣学習を用いて訓練する。
• 参考スコア（独自算出の注目度）: 29.29673962163146
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Integer programming (IP) is an important and challenging problem. Approximate methods have shown promising performance on both effectiveness and efficiency for solving the IP problem. However, we observed that a large fraction of variables solved by some iterative approximate methods fluctuate around their final converged discrete states in very long iterations. Inspired by this observation, we aim to accelerate these approximate methods by early fixing these fluctuated variables to their converged states while not significantly harming the solution accuracy. To this end, we propose an early fixing framework along with the approximate method. We formulate the whole early fixing process as a Markov decision process, and train it using imitation learning. A policy network will evaluate the posterior probability of each free variable concerning its discrete candidate states in each block of iterations. Specifically, we adopt the powerful multi-headed attention mechanism in the policy network. Extensive experiments on our proposed early fixing framework are conducted to three different IP applications: constrained linear programming, MRF energy minimization and sparse adversarial attack. The former one is linear IP problem, while the latter two are quadratic IP problems. We extend the problem scale from regular size to significantly large size. The extensive experiments reveal the competitiveness of our early fixing framework: the runtime speeds up significantly, while the solution quality does not degrade much, even in some cases it is available to obtain better solutions. Our proposed early fixing framework can be regarded as an acceleration extension of ADMM methods for solving integer programming. The source codes are available at \url{https://github.com/SCLBD/Accelerated-Lpbox-ADMM}.
• Abstract（参考訳）: 整数プログラミング(IP)は重要かつ困難な問題である。 近似法はIP問題の解法の有効性と効率性の両方において有望な性能を示した。 しかし、いくつかの反復近似法によって解かれた変数は、非常に長い反復で最終的な収束した離散状態の周りに変動する。 この観察に触発されて,これらの変動変数を収束状態に早期に固定し,解の精度を損なうことなく近似法を高速化することを目指している。 そこで本研究では,近似手法とともに早期修正フレームワークを提案する。 初期固定過程全体をマルコフ決定過程として定式化し,模倣学習を用いて学習する。 ポリシーネットワークは、各反復ブロックにおける各離散候補状態に関する各自由変数の後方確率を評価する。 具体的には、ポリシーネットワークにおいて、強力なマルチヘッドアテンションメカニズムを採用する。 提案した早期修正フレームワークに関する大規模な実験は,制約線形プログラミング,MDFエネルギー最小化,スパース対逆攻撃という3つの異なるIPアプリケーションに対して行われた。 前者は線形IP問題であり、後者は二次IP問題である。 問題尺度を通常のサイズからかなり大きなサイズに拡張します。 ランタイムは大幅にスピードアップしますが、ソリューションの品質はそれほど低下していません。 提案する初期修正フレームワークは、整数計画を解くためのadmm法の加速拡張と見なすことができる。 ソースコードは \url{https://github.com/SCLBD/Accelerated-Lpbox-ADMM} で入手できる。

関連論文リスト

• The Differentiable Feasibility Pump [49.55771920271201]
  本稿では,従来の実現可能性ポンプとその追随点の多くを,特定のパラメータを持つ勾配差アルゴリズムとみなすことができることを示す。 この再解釈の中心的な側面は、伝統的なアルゴリズムがそのコストに関して線形緩和の解を区別することを観察することである。
  論文  参考訳（メタデータ） (2024-11-05T22:26:51Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Integer Programming Using A Single Atom [0.0]
  我々は,IP問題を元の形で任意の量子システムにマップし,解くアルゴリズムを開発した。 最適解は、最大8つの変数と4つの制約を持つIP問題に対して数マイクロ秒以内に見つかる。
  論文  参考訳（メタデータ） (2024-02-26T12:59:20Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Fast and Robust Non-Rigid Registration Using Accelerated Majorization-Minimization [35.66014845211251]
  非剛性登録は、ターゲット形状と整合する非剛性な方法でソース形状を変形させるが、コンピュータビジョンにおける古典的な問題である。 既存のメソッドは通常$ell_p$型ロバストノルムを使用してアライメントエラーを測定し、変形の滑らかさを規則化する。 本稿では、アライメントと正規化のためのグローバルなスムーズなロバストノルムに基づく、ロバストな非剛体登録のための定式化を提案する。
  論文  参考訳（メタデータ） (2022-06-07T16:00:33Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
  そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。 本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
  論文  参考訳（メタデータ） (2021-10-21T18:05:40Z)
• Learning Pseudo-Backdoors for Mixed Integer Programs [48.36587539004464]
  そこで我々は,Mixed Programs (MIP) の解法として,擬似バックドア(擬似バックドア)と呼ばれる一連の決定変数の優先順位付けを学習し,解時間を短縮する機械学習手法を提案する。 我々のアプローチは、これらの変数の分岐のみが最適積分解と最適性の証明となるような、小さな変数の集合に対応する強いバックドアの概念から着想を得ている。 強力なバックドアに対する擬似バックドアの重要な利点は、データ駆動の識別や予測に非常に適している点である。
  論文  参考訳（メタデータ） (2021-06-09T13:59:53Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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