論文の概要: Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning
- arxiv url: http://arxiv.org/abs/2611.04230v1
- Date: Tue, 03 Nov 2026 03:10:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-11 00:57:52.442485
- Title: Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning
- Title（参考訳）: 完全分割によるQPLIB 2096の厳密な最適認証
- Abstract要約: 凍結した QPLIB096 インスタンスが地球規模で7,025,720 であるという正確な計算証明を示す。
結果は、正確かつ特異的な証人による、正確に特定された最適性証明であり、instanceパフォーマンスが描画される。
- 参考スコア（独自算出の注目度）: 7.932867767590172
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We present an exact computational proof that the frozen QPLIB_2096 instance has global minimum 7,025,720. The solution and certification approach was explored and refined through ZiYor, a self-evolving AI system. The authors provide the mathematical account and exact validation reported here. The original formulation has 300 binary variables, 6,900 triangle inequalities, and 25 nonconvex quadratic constraints. A coefficient-level reconstruction identifies its variables with the unordered pairs of 25 items. The triangle inequalities encode partitions, while each quadratic constraint becomes a bound on the total weight of edges incident to one partition block. This yields a set-partitioning formulation over all capacity-feasible blocks, with a separate edge-cost graph determining the objective. Exact enumeration examines 245,505 subsets of sizes one through six and finds 14,981 feasible blocks. Every six-element subset is infeasible; nonnegative capacity weights exclude all larger blocks. An integer price vector satisfies the dual inequality for every feasible block and has sum 2,229,456. Subtracting this sum from the total objective edge cost 9,255,176 gives a lower bound of 7,025,720, attained by the supplied six-block partition. Fresh solver-free checks validate the candidate against both frozen model formats and verify the certificate. The result is an instance-specific optimality proof with an exact primal and dual witness; no cross-instance performance conclusion is drawn.
- Abstract（参考訳）: 凍結したQPLIB_2096 インスタンスが、地球規模で7,025,720 であることを示す。
ソリューションと認定のアプローチは、自己進化型AIシステムであるZiYorを通じて探求され、洗練されました。
著者は、ここで報告された数学的説明と正確な検証を提供する。
元の定式化は300のバイナリ変数、6,900の三角形の不等式、25の非凸2次制約を持つ。
係数レベルの再構成は、25項目の順序のないペアで変数を識別する。
三角形の不等式はパーティションを符号化するが、各2次制約は1つのパーティションブロックに付随するエッジの総重みに束縛される。
これにより、すべてのキャパシティ実現可能なブロックに対する集合分割の定式化が得られ、目的を決定するエッジコストグラフが分離される。
Exact enumerationでは、サイズが1から6の245,505個のサブセットを調べ、14,981個の実行可能なブロックを見つける。
6要素の全ての部分集合は実現不可能であり、非負の容量重みは全ての大きなブロックを除外する。
整数価格ベクトルは、実現可能なブロックごとに双対不等式を満足し、合計は2,229,456である。
総対物エッジコスト9,255,176からこの和を差し引けば、供給された6ブロック分割で得られる7,025,720の下限が得られる。
フレッシュソルバフリーチェックは、両方の凍結モデルフォーマットに対して候補を検証し、証明書を検証する。
その結果、インスタンス固有の最適性証明であり、真に原始的かつ双対的な証人であり、クロスインスタンス性能の結論は導出されない。
関連論文リスト
- Topological Sheaves of Irreducibility: A Theoretical Framework for Multi-Agent Task Obstructions [43.56505337362239]
可視性のトポロジカルシーブは、互換性の障害をシステム能力から分離する。
コサイクルデータに対して、表現されたコホモロジークラスが消滅すると、コチェーンの実現は解決可能である。
状態保存ロバスト性チェックは、正確なパフォーマンスを維持するが、クラス保持アブレーションにコスト調整されない。
論文 参考訳（メタデータ） (2026-10-19T17:30:40Z) - The Ball and the Box: Two Geometries of Computation in Superposition [44.1417343664238]
期待される誤差数は、高い確率で出力の正しさよりも多くの次元を必要とする可能性がある。
2つの誤差基準の下でシャープ次元閾値を導出する。
この分析はまた、正確なシミュレーションに従って閾値付近の遷移を記述している。
論文 参考訳（メタデータ） (2026-10-08T11:34:22Z) - Beyond Accuracy: Prefix-Invariant Realizations of Low-Precision Fast Matrix Multiplication [13.460819902711838]
トークン行を混ぜた丸めの和は、初期の言語モデル出力に後続のトークンからのコントリビューションを残せることを示す。
Qwen2.5-14B-Instructでは、2つの高速なFP8実現法が通常の精度で修復された。
トークン列を独立に量子化する有界整数符号上での2レベルストラッセンの証明付き実現法を構築する。
論文 参考訳（メタデータ） (2026-09-30T14:20:37Z) - On the SoS Certifiability of Log-Concave Distributions [51.56484100374058]
圏 $(Cm)m|v|m - mathbbE_Xsim Plangle X,vranglem$ は、すべての偶数 mge2$ に対する平方の和であり、$C>0$ は普遍定数である。
これにより、コタリとシュタインハルト(arXiv:1711.07465)の定理におけるポアンカレ定数への依存を排除し、対数凹面分布の最適モーメント境界を回復する。
論文 参考訳（メタデータ） (2026-09-24T16:48:02Z) - Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates [7.711757703549023]
有限ハイパーグラフにおける最大強独立集合問題について検討する。
本稿では,この問題に対する入射構造ツールキットを開発した。
アルゴリズム解析には、実現可能性、最大性、条件最適性、階層化された目撃者マッチング上界、入射局所複雑性境界が含まれる。
論文 参考訳（メタデータ） (2026-09-16T00:23:23Z) - Observational Indistinguishability and Integrity Blind Regions in Hybrid Quantum-Classical Workflows [0.0]
本稿では,ハイブリッド量子古典的ワークフロー整合性のためのクレーム相対的エビデンス/参照フレームワークを提案する。
観測上の不明瞭さは、有限バッチ統計ミスとは異なる構造的な盲点をもたらす。
論文 参考訳（メタデータ） (2026-09-15T13:16:37Z) - DODR: Deterministic Operator-Driven Reasoning in Latent Space [0.0]
本稿では,ラテントスペースアーキテクチャにおける決定論的演算子駆動推論を提案する。
高次元線形代数空間における推論グラフ計算としての推論を再構成する。
このアーキテクチャは構造的ゼロハロシン化保証と3層連続学習機構を提供する。
論文 参考訳（メタデータ） (2026-09-04T06:20:35Z) - Machine-Checked Certificates for the Geometric Half of the Minimum Kochen-Specker Bound [0.0]
mathbbR3$ の最小コシェン=スペクターベクトル系に対する最もよく知られた下界は、半分が DRAT を出力するが、幾何的半分がそうでないような計算証明に依存する。
正則な正則な正則ケースツリー証明を導入し、その分割は分解因子と正則な二乗分解である。
すべての証明書、チェッカー、証明は、単一のビルドから利用可能で、再生可能である。
論文 参考訳（メタデータ） (2026-07-29T02:53:00Z) - Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
有限オートマトンとして表現可能な任意の制約の下で,制約付き平均場後部からサンプリングする,正確かつトラクタブルなアルゴリズムを提案する。
このアプローチは、構築による制約満足度を保証し、欲求とサンプリングベースのデコーディングの両方をサポートし、並列およびブロックワイドデコーディングと互換性がある。
Dream-7B と LLaDA-8 の実証的な評価は、様々なタスクにおいてかなりの精度の向上を示した。
論文 参考訳（メタデータ） (2026-07-08T05:48:57Z) - Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization [43.74656748515853]
非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。
a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
論文 参考訳（メタデータ） (2023-05-30T04:10:11Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。