論文の概要: MILP-StuDio: MILP Instance Generation via Block Structure Decomposition

• arxiv url: http://arxiv.org/abs/2410.22806v1
• Date: Wed, 30 Oct 2024 08:33:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-31 14:26:18.820631
• Title: MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
• Title（参考訳）: MILP-StuDio: ブロック構造分解によるMILPインスタンス生成
• Authors: Haoyang Liu, Jie Wang, Wanbo Zhang, Zijie Geng, Yufei Kuang, Xijun Li, Bin Li, Yongdong Zhang, Feng Wu,
• Abstract要約: Mixed-integer linear programming (MILP) は、多くの応用において最も一般的な数学的定式化の1つである。 我々は,ブロック構造を保存して高品質なインスタンスを生成するために,ブロック構造分解(MILP-StuDio)と呼ばれる新しいMILP生成フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 55.79888361191114
• License:
• Abstract: Mixed-integer linear programming (MILP) is one of the most popular mathematical formulations with numerous applications. In practice, improving the performance of MILP solvers often requires a large amount of high-quality data, which can be challenging to collect. Researchers thus turn to generation techniques to generate additional MILP instances. However, existing approaches do not take into account specific block structures -- which are closely related to the problem formulations -- in the constraint coefficient matrices (CCMs) of MILPs. Consequently, they are prone to generate computationally trivial or infeasible instances due to the disruptions of block structures and thus problem formulations. To address this challenge, we propose a novel MILP generation framework, called Block Structure Decomposition (MILP-StuDio), to generate high-quality instances by preserving the block structures. Specifically, MILP-StuDio begins by identifying the blocks in CCMs and decomposing the instances into block units, which serve as the building blocks of MILP instances. We then design three operators to construct new instances by removing, substituting, and appending block units in the original instances, enabling us to generate instances with flexible sizes. An appealing feature of MILP-StuDio is its strong ability to preserve the feasibility and computational hardness of the generated instances. Experiments on the commonly-used benchmarks demonstrate that using instances generated by MILP-StuDio is able to significantly reduce over 10% of the solving time for learning-based solvers.
• Abstract（参考訳）: Mixed-integer linear programming (MILP) は、多くの応用において最も一般的な数学的定式化の1つである。 実際には、MILPソルバの性能向上には、しばしば大量の高品質なデータを必要とするため、収集は困難である。 これにより、研究者は新たなMILPインスタンスを生成するために生成技術に目を向ける。 しかし、既存の手法は、MILPの制約係数行列(CCM)において、問題定式化と密接に関連している特定のブロック構造を考慮に入れていない。 その結果、ブロック構造の破壊や問題定式化により、計算的に自明な、あるいは実現不可能なインスタンスを生成する傾向にある。 この課題に対処するために、ブロック構造を保存して高品質なインスタンスを生成するために、ブロック構造分解(MILP-StuDio)と呼ばれる新しいMILP生成フレームワークを提案する。 具体的には、MILP-StuDioは、CCMのブロックを特定し、インスタンスをブロック単位に分解することから始まり、MILPインスタンスのビルディングブロックとして機能する。 次に、元のインスタンスにブロックユニットを削除、置換、追加することで、新しいインスタンスを構築するために3つのオペレータを設計します。 MILP-StuDioの魅力的な特徴は、生成されたインスタンスの実現可能性と計算困難性を維持する強力な能力である。 一般的に使用されているベンチマークの実験では、MILP-StuDioによって生成されたインスタンスを使用することで、学習ベースの問題解決者の解決時間の10%を大幅に削減できることが示された。

関連論文リスト

• Tender: Accelerating Large Language Models via Tensor Decomposition and Runtime Requantization [0.6445087473595953]
  大規模言語モデル(LLM)は、機械学習における様々なタスクにおいて優れたパフォーマンスを示す。 LLM推論のデプロイは、高い計算とメモリ要求のために問題となる。 我々は,低精度でLLM推論を効率的に展開できるアルゴリズム-ハードウェア共設計ソリューションであるテンダーを提案する。
  論文  参考訳（メタデータ） (2024-06-16T09:51:55Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  本稿では、新しいアルゴリズムを用いて、弱監督(GLWS)から学習するための一般的な枠組みを紹介する。 GLWSの中心は期待最大化(EM)の定式化であり、様々な弱い監督源を順応的に収容している。 また,EM計算要求を大幅に単純化する高度なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-02T21:48:50Z)
• A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability [66.37474135424637]
  我々は、MILPインスタンスのための最初の深層生成フレームワークであるG2MILPを提案する。 G2MILPはMILPインスタンスを二部グラフとして表現し、マスク付き変分オートエンコーダを元のグラフの一部を反復的に破損させ、置き換えて新しいグラフを生成する。 生成されたMILPインスタンスの品質を評価するためのベンチマークスイートを設計する。
  論文  参考訳（メタデータ） (2023-10-04T13:34:34Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach [73.62265030773652]
  ブロック構造力学を用いたマルコフ決定過程における効率的な強化学習アルゴリズムであるBRIEEを提案する。 BRIEEは、潜伏状態の発見、探索、搾取を相互にインターリーブし、ほぼ最適な政策を確実に学べる。 我々は、BRIEEが最先端のBlock MDPアルゴリズムであるHOMER RLや、リッチ・オブザーブレーションの組み合わせロック問題に挑戦する経験的ベースラインよりも、より標本効率が高いことを示す。
  論文  参考訳（メタデータ） (2022-01-31T19:47:55Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  フェデレーテッド・ラーニング(FL)はパラメータ伝達中にFLモデルに対する外部攻撃に対して脆弱である。 本稿では,最先端の防御アグリゲーション機構に対処する有効なMPアルゴリズムを提案する。 実験の結果,提案したCMPアルゴリズムは,既存の攻撃機構よりも効果的で,かなり優れていることが示された。
  論文  参考訳（メタデータ） (2021-01-28T03:28:18Z)
• On Application of Block Kaczmarz Methods in Matrix Factorization [2.335152769484957]
  行列分解のための共通交互スキームにおいて、最小二乗のサブルーチンを置換するブロックKaczmarzソルバについて議論する。 実行時と動作中のメモリ要件のごく一部に対して、最小二乗問題の解法に匹敵するソリューションを生成するブロックサイズを見つけます。
  論文  参考訳（メタデータ） (2020-10-20T21:29:50Z)
• Binary matrix factorization on special purpose hardware [5.926928436252818]
  データマイニングに多くの応用がある重要なバイナリ行列分解(BMF)問題に焦点をあてる。 BMFのための2つのQUBO定式化を提案し、これらの定式化にクラスタリング制約をどのように組み込むかを示す。 また,いくつかの状況において,より洗練された手法よりも優れた単純なベースラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-17T01:44:24Z)
• Exploring Instance Generation for Automated Planning [1.6735240552964108]
  制約プログラミングと自動計画はこれらの分野の例である。 各解法の効率は、問題間だけでなく、同じ問題のインスタンス間でも異なる。 本稿では,Essenceを用いて計画上の問題記述全体をモデル化する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-21T19:58:33Z)

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

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