論文の概要: A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem

• arxiv url: http://arxiv.org/abs/2512.15198v1
• Date: Wed, 17 Dec 2025 08:49:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-18 17:06:26.906002
• Title: A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem
• Title（参考訳）: 最大重み付き独立集合問題に対する緩和決定図のクラスタリングに基づく可変順序付けフレームワーク
• Authors: Mohsen Nafar, Michael Römer, Lin Xie,
• Abstract要約: この研究は、変数順序付けのための新しいクラスタリングベースのフレームワークを導入する。 固定されていない変数の完全な集合に動的順序付けを適用する代わりに、最初にプリミティブ変数をクラスタに配置する。 次に、この構造分解を利用して順序付けプロセスの導出を行い、分割の探索空間を著しく削減する。
• 参考スコア（独自算出の注目度）: 4.312746668772342
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient exact algorithms for Discrete Optimization (DO) rely heavily on strong primal and dual bounds. Relaxed Decision Diagrams (DDs) provide a versatile mechanism for deriving such dual bounds by compactly over-approximating the solution space through node merging. However, the quality of these relaxed diagrams, i.e. the tightness of the resulting dual bounds, depends critically on the variable ordering and the merging decisions executed during compilation. While dynamic variable ordering heuristics effectively tighten bounds, they often incur computational overhead when evaluated globally across the entire variable set. To mitigate this trade-off, this work introduces a novel clustering-based framework for variable ordering. Instead of applying dynamic ordering heuristics to the full set of unfixed variables, we first partition variables into clusters. We then leverage this structural decomposition to guide the ordering process, significantly reducing the heuristic's search space. Within this framework, we investigate two distinct strategies: Cluster-to-Cluster, which processes clusters sequentially using problem-specific aggregate criteria (such as cumulative vertex weights in the Maximum Weighted Independent Set Problem (MWISP)), and Pick-and-Sort, which iteratively selects and sorts representative variables from each cluster to balance local diversity with heuristic guidance. Later on, developing some theoretical results on the growth of the size of DDs for MWISP we propose two different policies for setting the number of clusters within the proposed framework. We embed these strategies into a DD-based branch-and-bound algorithm and evaluate them on the MWISP. Across benchmark instances, the proposed methodology consistently reduces computational costs compared to standard dynamic variable ordering baseline.
• Abstract（参考訳）: 離散最適化(DO)の効率的な正確なアルゴリズムは、強い原始境界と双対境界に大きく依存している。 Relaxed Decision Diagrams (DDs) は、ノードのマージによって解空間をコンパクトに過剰に近似することにより、そのような双対境界を導出するための汎用的なメカニズムを提供する。 しかし、これらの緩和ダイアグラムの品質、すなわち結果の双対境界の厳密さは、コンパイル中に実行される変数の順序付けとマージ決定に批判的に依存する。 動的変数順序ヒューリスティックは境界を効果的に締め付けるが、変数集合全体にわたって世界規模で評価すると計算オーバーヘッドが発生することが多い。 このトレードオフを緩和するために、変数順序付けのための新しいクラスタリングベースのフレームワークを導入する。 固定されていない変数の完全な集合に動的順序付けヒューリスティックを適用する代わりに、まず変数をクラスタに分割する。 次に、この構造分解を利用して順序付け過程を導出し、ヒューリスティックな探索空間を著しく減少させる。 本枠組みでは,各クラスタから代表変数を反復的に選択・選別し,局所的な多様性とヒューリスティックガイダンスのバランスをとるクラスタ・ツー・クラスタを,問題固有の集約基準(最大重み付き独立集合問題(MWISP)の累積頂点重みなど)を用いて逐次クラスタ処理するクラスタ・ツー・クラスタと,各クラスタから代表変数を反復的に選択・選別するピック・アンド・ソルトの2つの戦略について検討する。 その後,MWISP 用 DD の規模拡大に関する理論的結果が開発され,提案フレームワーク内にクラスタ数を設定するための2つの異なるポリシーが提案されている。 これらの戦略をDDベースの分岐結合アルゴリズムに組み込んでMWISP上で評価する。 ベンチマークインスタンス全体で、提案手法は標準動的変数順序付けベースラインと比較して計算コストを一貫して削減する。

関連論文リスト

• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version) [50.41628860536753]
  本稿では,SCMax と呼ばれる自己教師型コンセンサス最大化による,新しい完全パラメータフリークラスタリングフレームワークを提案する。 本フレームワークは,階層的なクラスタリングとクラスタ評価を単一の統合プロセスで行う。
  論文  参考訳（メタデータ） (2025-11-12T11:17:17Z)
• Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
  コクラスタリング(co-clustering)または双方向クラスタリング( two-way clustering)とも呼ばれるビクラスタリングは、データマトリックスの行と列を同時にパーティショニングすることで、コヒーレントパターンによるサブマトリクスを明らかにする。 我々は、オブジェクトが同一または異なるビクラスタに属するべきか否かを規定する制約付きビクラスタリング、すなわち、マスタリンクとナントリンクの制約について研究する。
  論文  参考訳（メタデータ） (2025-08-07T15:29:22Z)
• Deep Matrix Factorization with Adaptive Weights for Multi-View Clustering [0.6037276428689637]
  DMFAW(Adaptive Weights for Multi-View Clustering)を用いた新しいDeep Matrix Factorizationを提案する。 提案手法は特徴選択を同時に組み込んで局所分割を生成し,クラスタリング結果を向上する。 ベンチマークデータセットの実験では、DMFAWがクラスタリングのパフォーマンスで最先端のメソッドより優れていることが強調されている。
  論文  参考訳（メタデータ） (2024-12-03T09:08:27Z)
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• High-dimensional variable clustering based on maxima of a weakly dependent random process [1.1999555634662633]
  本稿では,Asymptotic Independent Block (AI-block)モデルと呼ばれる,変数クラスタリングのための新しいモデルのクラスを提案する。 このモデルのクラスは特定可能であり、つまり、分割の間に部分的な順序を持つ極大要素が存在し、統計的推測が可能であることを意味する。 また,変数のクラスタを列挙するチューニングパラメータに依存するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-02T08:24:26Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)

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

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