論文の概要: Certified Symmetry and Dominance Breaking for Combinatorial Optimisation

• arxiv url: http://arxiv.org/abs/2203.12275v3
• Date: Wed, 16 Aug 2023 09:34:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-17 18:12:44.271878
• Title: Certified Symmetry and Dominance Breaking for Combinatorial Optimisation
• Title（参考訳）: 組合せ最適化のための認証対称性と支配破壊
• Authors: Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, Jakob Nordstr\"om
• Abstract要約: 本研究では,対称性と支配的破壊が容易に表現可能な最適化問題に対する認証手法を開発した。 提案手法は,提案手法が幅広い問題に適用可能であることを示す概念実証として,最大斜め解法と制約法に適用する。
• 参考スコア（独自算出の注目度）: 13.333957453318744
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Symmetry and dominance breaking can be crucial for solving hard combinatorial search and optimisation problems, but the correctness of these techniques sometimes relies on subtle arguments. For this reason, it is desirable to produce efficient, machine-verifiable certificates that solutions have been computed correctly. Building on the cutting planes proof system, we develop a certification method for optimisation problems in which symmetry and dominance breaking are easily expressible. Our experimental evaluation demonstrates that we can efficiently verify fully general symmetry breaking in Boolean satisfiability (SAT) solving, thus providing, for the first time, a unified method to certify a range of advanced SAT techniques that also includes XOR and cardinality reasoning. In addition, we apply our method to maximum clique solving and constraint programming as a proof of concept that the approach applies to a wider range of combinatorial problems.
• Abstract（参考訳）: 対称性と支配的破壊は、厳密な組合せ探索と最適化問題を解決するために重要であるが、これらの手法の正しさは微妙な議論に依存することがある。 このため、解が正しく計算された効率的な機械検証証明書を作成することが望ましい。 切削面証明システムに基づいて,対称性と支配的破壊が容易に表現可能な最適化問題に対する認証手法を開発した。 実験により, ブール充足可能性 (SAT) の解法において, 完全一般対称性の破れを効果的に検証できることが確認された。 さらに,本手法を,より広範な組合せ問題に適用できるという概念実証として,最大傾き解法と制約プログラミングに適用する。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  本稿では,ハイパーキューブやトーラス上のスムーズな関数を扱う証明書を用いた非キューブ最適化手法を提案する。 スペクトルの減衰に固有の対象関数の正則性を活用することにより、正確な証明を取得し、高度で強力なニューラルネットワークを活用することができる。
  論文  参考訳（メタデータ） (2023-06-26T09:42:59Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Analyzing Inexact Hypergradients for Bilevel Learning [0.09669369645900441]
  暗黙の関数定理と自動微分/バックプロパゲーションに基づいて既存の手法を一般化する過次計算のための統一的なフレームワークを提案する。 計算結果から,高次アルゴリズムの選択は低次解法の選択と同等に重要であることが明らかとなった。
  論文  参考訳（メタデータ） (2023-01-11T23:54:27Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Accelerating Certifiable Estimation with Preconditioned Eigensolvers [2.1701691499017812]
  多くの最先端 (Burer-Monteiro 因数分解に基づく) 推定手法における主要なコストは、解の検証である。 本稿では,この検証ステップを著しく高速化する方法を示し,検証手法の全体的な高速化について述べる。 事前条件付き固有解法を用いてこの問題に対処する方法を示す。
  論文  参考訳（メタデータ） (2022-07-12T02:00:08Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control [7.347989843033034]
  本稿では,最小化問題を大まかに解決するオラクルのみに依存するサドル点最適化手法を提案する。 我々は、その収束特性を強い凸-凹問題で解析し、その線形収束性を大域的なmin-maxサドル点へ示す。 1+1)-CMA-ES を最小化オラクル、すなわち Adversarial-CMA-ES として開発した手法の実装は、テスト問題に対する既存のアプローチよりも優れている。
  論文  参考訳（メタデータ） (2021-05-25T00:08:47Z)
• A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization [5.460573052311485]
  本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。 通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-27T07:15:25Z)

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

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