論文の概要: Branch-and-cut algorithms for colorful components problems

• arxiv url: http://arxiv.org/abs/2408.16508v1
• Date: Thu, 29 Aug 2024 13:10:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-30 13:42:55.079011
• Title: Branch-and-cut algorithms for colorful components problems
• Title（参考訳）: カラフルなコンポーネント問題に対するブランチ・アンド・カットアルゴリズム
• Authors: Claudia Archetti, Martina Cerulli, Carmine Sorgente,
• Abstract要約: 我々は,各ノードに色を割り当てる色付きグラフを,カラフルな連結成分に分割しなければならない3つの最適化問題に取り組む。 これらの問題は、コミュニティ検出、サイバーセキュリティ、バイオインフォマティクスに応用されている。 整数非線型定式化(英語版)を行い、標準手法を用いて線形化する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle three optimization problems in which a colored graph, where each node is assigned a color, must be partitioned into colorful connected components. A component is defined as colorful if each color appears at most once. The problems differ in the objective function, which determines which partition is the best one. These problems have applications in community detection, cybersecurity, and bioinformatics. We present integer non-linear formulations, which are then linearized using standard techniques. To solve these formulations, we develop exact branch-and-cut algorithms, embedding various improving techniques, such as valid inequalities, bounds limiting the number of variables, and warm-start and preprocessing techniques. Extensive computational tests on benchmark instances demonstrate the effectiveness of the proposed procedures. The branch-and-cut algorithms can solve reasonably sized instances efficiently. To the best of our knowledge, we are the first to propose an exact algorithm for solving these problems.
• Abstract（参考訳）: 我々は,各ノードに色を割り当てる色付きグラフを,カラフルな連結成分に分割しなければならない3つの最適化問題に取り組む。 コンポーネントは、各色が最大で一度だけ現れる場合、カラフルなものとして定義される。 問題は目的関数で異なり、どの分割が最適かを決定する。 これらの問題は、コミュニティ検出、サイバーセキュリティ、バイオインフォマティクスに応用されている。 整数非線型定式化(英語版)を行い、標準手法を用いて線形化する。 これらの定式化を解決するために,正当性不等式,変数数制限境界,ウォームスタート・プリプロセッシングといった様々な改良手法を組み込んだ,正確な分岐・カットアルゴリズムを開発した。 ベンチマークインスタンスの大規模な計算テストでは,提案手法の有効性が示されている。 ブランチ・アンド・カットのアルゴリズムは、合理的なサイズのインスタンスを効率的に解くことができる。 我々の知る限りでは、これらの問題を解決するための正確なアルゴリズムを最初に提案する。

関連論文リスト

• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。 本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
  論文  参考訳（メタデータ） (2024-08-02T18:02:51Z)
• Exploratory Landscape Analysis for Mixed-Variable Problems [0.7252027234425334]
  決定空間が連続変数、バイナリ変数、整数変数、カテゴリー変数の混合である混合変数問題に対する探索的景観特徴を計算する手段を提供する。 実用化のためのメリットをさらに強調するため,自動アルゴリズム選択研究を設計・実施する。 トレーニングされたアルゴリズムセレクタは、すべてのベンチマーク問題に対して、単一のベストと仮想ベストのギャップを57.5%縮めることができる。
  論文  参考訳（メタデータ） (2024-02-26T10:19:23Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
  Invexプログラムは、固定点ごとに世界最小値が得られる特別な非制約問題である。 そこで我々は,超凸問題における一般収束率を解くために,新しい一階法アルゴリズムを提案する。 提案アルゴリズムは,制約付き凸プログラムを解く最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-10T10:11:01Z)
• Experience in Engineering Complex Systems: Active Preference Learning with Multiple Outcomes and Certainty Levels [1.5257326975704795]
  ブラックボックス最適化とは、目的関数と/または制約集合が未知、到達不能、あるいは存在しない問題を指す。 この特定の情報を活用するために、いわゆるActive Preference Learningと呼ばれるアルゴリズムが開発された。 我々のアプローチは、さらなる情報を効果的に活用できるような方法でアルゴリズムを拡張することを目的としている。
  論文  参考訳（メタデータ） (2023-02-27T15:55:37Z)
• Differentiable Mathematical Programming for Object-Centric Representation Learning [32.76702197616919]
  本稿では,線形プログラムとして表現される分割法として最小$s$-$t$グラフカットを提案する。 このグラフを解くために、我々の解は効率的でスケーラブルで微分可能な二次プログラミング近似に依存する。 以上の結果から,我々の手法はスケーラブルであり,テクスチャ化されたシーンやオブジェクトを用いたオブジェクト発見タスクにおいて,既存の手法よりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2022-10-05T11:36:45Z)
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems [0.0]
  離散最適化問題(整数型最適化問題)を直感的に合成・解析する手法を提案する。 この方法は、符号化に依存しない離散量子中間表現(DQIR)を用いて表現される。 第二に、複数のランタイムエンコーディングを比較した数値的研究を行う。 第3に、我々は16レベルの量子変数までの低深度グラフ由来部分ミキサー(GDPM)を設計する。
  論文  参考訳（メタデータ） (2022-03-28T01:01:12Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。 本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
  論文  参考訳（メタデータ） (2021-07-20T11:23:21Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。 我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。 実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
  論文  参考訳（メタデータ） (2020-07-05T15:23:33Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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