論文の概要: Moving between high-quality optima using multi-satisfiability characteristics in hard-to-solve Max3Sat instances
- arxiv url: http://arxiv.org/abs/2504.11864v1
- Date: Wed, 16 Apr 2025 08:38:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-17 14:39:53.466912
- Title: Moving between high-quality optima using multi-satisfiability characteristics in hard-to-solve Max3Sat instances
- Title（参考訳）: 難解Max3Satインスタンスにおける多相性特性を用いた高品質最適移動
- Authors: J. Piatek, M. W. Przewozniczek, F. Chicano, R. Tinós,
- Abstract要約: トンネリングが失敗するMax3Satインスタンスに焦点をあて、局所最適高品質ソリューションとグローバル最適ソリューションの領域間の移動を改善する。
本稿では,高品質な解を解空間から遠ざかる接続を可能にする,節適合性特性の操作を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Gray-box optimization proposes effective and efficient optimizers of general use. To this end, it leverages information about variable dependencies and the subfunction-based problem representation. These approaches were already shown effective by enabling \textit{tunnelling} between local optima even if these moves require the modification of many dependent variables. Tunnelling is useful in solving the maximum satisfiability problem (MaxSat), which can be reformulated to Max3Sat. Since many real-world problems can be brought to solving the MaxSat/Max3Sat instances, it is important to solve them effectively and efficiently. Therefore, we focus on Max3Sat instances for which tunnelling fails to introduce improving moves between locally optimal high-quality solutions and the region of globally optimal solutions. We analyze the features of such instances on the ground of phase transitions. Based on these observations, we propose manipulating clause-satisfiability characteristics that allow connecting high-quality solutions distant in the solution space. We utilize multi-satisfiability characteristics in the optimizer built from typical gray-box mechanisms. The experimental study shows that the proposed optimizer can solve those Max3Sat instances that are out of the grasp of state-of-the-art gray-box optimizers. At the same time, it remains effective for instances that have already been successfully solved by gray-box.
- Abstract（参考訳）: グレーボックス最適化は、汎用の効率的かつ効率的な最適化手法を提案する。
この目的のために、変数依存とサブファンクションベースの問題表現に関する情報を活用する。
これらの動きが多くの依存変数の修正を必要とする場合でも、局所最適点間の \textit{tunnelling} を有効にすることで、これらのアプローチは既に効果的に示されていた。
トンネルは最大満足度(MaxSat)問題(Max3Sat)を解決するのに有用である。
多くの実世界の問題がMaxSat/Max3Satインスタンスの解決に導かれるため、効率よく効率的に解決することが重要である。
そこで我々は,局所最適高品位解とグローバル最適解の領域間の移動を改善するためにトンネルが失敗するMax3Satインスタンスに着目した。
位相遷移に基づいて,そのようなインスタンスの特徴を解析する。
これらの観測に基づいて,高品質な溶液を解空間から遠ざかる接続を可能にする節満足度特性の操作を提案する。
典型的なグレーボックス機構から構築したオプティマイザにおいて,多相性特性を利用する。
実験により、提案したオプティマイザは、最先端のグレーボックスオプティマイザを把握できないMax3Satインスタンスを解くことができることが示された。
同時に、グレーボックスによってすでに解決されたインスタンスにも有効である。
関連論文リスト
- Self-Adaptive Ising Machines for Constrained Optimization [0.4450107621124637]
制約のラグランジュ緩和を用いてエネルギー景観を形作る自己適応型IMを提案し, 罰則の事前調整を回避する。
我々は,多次元クナップサック問題 (MKP) と二次クナップサック問題 (QKP) でアルゴリズムをベンチマークし,後者は線形制約を持つイジング問題である。
その結果,探索中にエネルギー環境に適応することで,制約付き最適化のためにIMを高速化できることが示唆された。
論文 参考訳（メタデータ） (2025-01-09T05:02:50Z) - Global Optimization: A Machine Learning Approach [7.052596485478637]
Bertsimas と Ozturk (2023) は、ブラックボックスのグローバル最適化問題を解決する方法として OCTHaGOn を提案した。
我々は、他のMIO表現可能なMLモデルを用いて、元の問題を近似することで、このアプローチの拡張を提供する。
多くの場合において、ソリューションの実現可能性と最適性の改善を示す。
論文 参考訳（メタデータ） (2023-11-03T06:33:38Z) - Balancing Utility and Fairness in Submodular Maximization (Technical
Report) [27.20340546154524]
実用性と公平性のバランスをとるために,emphBi Maxim Submodularization (BSM) と呼ばれる新しい問題を提案する。
BSMは任意の定数係数で近似できないため、効率的なインスタンス依存近似スキームの設計に焦点をあてる。
論文 参考訳（メタデータ） (2022-11-02T09:38:08Z) - A Framework for Inherently Interpretable Optimization Models [0.0]
何十年も前に難解だった大規模な問題の解決は、今や日常的な課題である。
1つの大きな障壁は、最適化ソフトウェアがブラックボックスとして認識できることである。
本稿では、本質的に理解しやすい説明規則を持つ解を導出する最適化フレームワークを提案する。
論文 参考訳（メタデータ） (2022-08-26T10:32:00Z) - Bayesian Optimization for Min Max Optimization [77.60508571062958]
そこで我々は,最適化すべき関数が事前に分かっていないような設定でMin Max Optimizationを実行するアルゴリズムを提案する。
我々は,改善を期待する2つの獲得機能とガウス過程の上部信頼境界を拡張した。
これらの取得機能は、ベンチマーク設定よりも高速に収束する、より良いソリューションを可能にすることを示す。
論文 参考訳（メタデータ） (2021-07-29T06:49:34Z) - DC3: A learning method for optimization with hard constraints [85.12291213315905]
この問題に対処するアルゴリズムとして,Deep Constraint Completion and Correction (DC3)を提案する。
DC3は、等式制約を満たす部分解と不等式制約を満たすアンロールベースの補正を暗黙的に完成する。
合成最適化タスクとAC最適電力流の実世界設定の両方でDC3の有効性を実証します。
論文 参考訳（メタデータ） (2021-04-25T18:21:59Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Hybrid Framework Using a QUBO Solver For Permutation-Based
Combinatorial Optimization [5.460573052311485]
本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。
通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
論文 参考訳（メタデータ） (2020-09-27T07:15:25Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Bilevel Optimization for Differentially Private Optimization in Energy
Systems [53.806512366696275]
本稿では,入力に敏感な制約付き最適化問題に対して,差分プライバシーを適用する方法について検討する。
本稿は, 自然仮定の下では, 大規模非線形最適化問題に対して, 双レベルモデルを効率的に解けることを示す。
論文 参考訳（メタデータ） (2020-01-26T20:15:28Z) - Optimizing Wireless Systems Using Unsupervised and
Reinforced-Unsupervised Deep Learning [96.01176486957226]
無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。
本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
論文 参考訳（メタデータ） (2020-01-03T11:01:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。