論文の概要: Hard Instances on Demand

• arxiv url: http://arxiv.org/abs/2610.22637v1
• Date: Thu, 15 Oct 2026 20:47:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 00:56:07.666907
• Title: Hard Instances on Demand
• Title（参考訳）: 需要のハードインスタンス
• Abstract要約: 我々は、Nevergrad最適化プラットフォーム上に構築された、広く適用可能なワークフローを開発する。 本報告では, 満足度, 旅行セールスパーソン, ハミルトニアンサイクル, フローホップスケジューリングの4つの問題について実演する。 われわれの進化したインスタンスは、4つのケーススタディのすべてにおいて、予算に適合したランダムな引き分けの難易度を3桁以上上回った。
• 参考スコア（独自算出の注目度）: 1.279550134588484
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The conclusions of an experimental study of algorithms are only as good as the instances they are run on. Benchmark libraries for well-studied problems took decades to curate, while evaluations of new problems often fall back on random instances, which are known to be misleading: they may say more about the random generator than about the algorithmic question at hand. We treat instance generation as an optimization problem: parameterize the instance space, take the solver's running time as the objective, and let a black-box optimizer search for hard instances. We develop a widely applicable workflow built on the Nevergrad optimization platform and demonstrate it on four NP-hard problems: satisfiability, traveling salesperson, Hamiltonian cycle, and non-permutation flow-shop scheduling. The search needs only the solver, an instance encoder, and a compute budget. Our evolved instances beat the hardest instance of a budget-matched random draw in all four case studies, by an order of magnitude or more in three. They are often competitive with long-curated benchmark sets: our SAT champion is harder (for a three-solver portfolio) than 78% of the 498 SAT Competition formulas in its size class; our 20-city TSP champions take several times longer than the hardest measured classical TSPLIB instance (229 cities); and our flow-shop champion takes 238.6 seconds of CP Optimizer time to solve to proven optimality (versus 4.5 seconds for the hardest of 100,000 random draws) while denying CP-SAT an optimality proof. The optimizer even recovers known structure from running time alone: it locates a SAT clause/variable ratio near the phase transition and finds structurally different champions for the two scheduling engines.
• Abstract（参考訳）: 実験的なアルゴリズムの研究の結論は、それらが実行されているインスタンスと同程度にしかありません。 十分に研究された問題に対するベンチマークライブラリは、何十年もかけてキュレートされるが、新しい問題の評価は、しばしばランダムなインスタンスに逆戻りし、これは誤解を招くことが知られている。 インスタンス空間をパラメータ化し、ソルバの実行時間を目的として取り、ブラックボックスオプティマイザにハードインスタンスを検索させます。 我々は、Nevergrad最適化プラットフォーム上に構築された広く適用可能なワークフローを開発し、満足度、旅行セールスパーソン、ハミルトンサイクル、非置換フローショップスケジューリングの4つのNPハードな問題を実演する。 検索には、ソルバ、インスタンスエンコーダ、計算予算のみが必要である。 われわれの進化したインスタンスは、4つのケーススタディのすべてにおいて、予算に適合したランダムな引き分けの難易度を3桁以上上回った。 SATチャンピオンは、サイズクラスの498 SATコンペティションの78%よりも難しい(3倍のポートフォリオ)、20都市TSPチャンピオンは、最も難しい古典的TSPLIBインスタンス(229都市)よりも数倍長くかかる、フローショップチャンピオンは、238.6秒のCP最適化時間(10万のランダムな引き分けで4.5秒以上)を、CP-SATは最適性を否定する。 このオプティマイザは、既知構造を実行時のみから復元し、位相遷移の近傍にSAT節/可変比を配置し、2つのスケジューリングエンジンの構造的に異なるチャンピオンを見つける。

関連論文リスト

• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints [0.0]
  NP完全満足度問題 3-SAT の局所探索を導入,ベンチマークする。 私たちの建設は、WalkSATのような確立した従来のアプローチが、地元のミニマで立ち往生する傾向にあるという決定的な観察に基づいています。 我々は,N=15000までの様々な問題サイズを持つ3SATインスタンスをランダムに生成したサンプルを用いて,アルゴリズムを解析・ベンチマークする。
  論文  参考訳（メタデータ） (2025-06-18T18:00:01Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering [6.86850788361785]
  本研究では,Grover Quantum Approximate Optimization Algorithm (G-QAOA) の2次高速化の数値的証拠を示す。 G-QAOAはGroverのアルゴリズムよりもリソース集約性が低く、3-SATやMax-SATに適応しやすい。 また、小さなインスタンスに対してIonQ Aria量子コンピュータのG-QAOAの利点を観察し、現在のハードウェアが全てのソリューションを決定・サンプリングするのに十分であることを示した。
  論文  参考訳（メタデータ） (2024-02-04T19:01:27Z)
• Online Learning for Scheduling MIP Heuristics [15.599296461516982]
  そこで本稿では,問題の解決を手元にある単一インスタンスに適応させるオンライン学習手法を提案する。 一般的に使われている静的ハンドリングを過去の観測を活かした適応フレームワークに置き換える。 解決に少なくとも1000秒を要した難しいインスタンスに対しては、4%のスピードアップを観察する。
  論文  参考訳（メタデータ） (2023-04-04T14:55:15Z)
• Towards an Understanding of Long-Tailed Runtimes of SLS Algorithms [0.0]
  GapSATソルバは、SLSソルバの性能を平均的に向上させる方法として、追加情報を学習した。 本稿では論理的に等価な問題定式化を生成する方法を提案する。 シュオニングのランダムウォークアルゴリズムのランタイムは約 Johnson SB であることを示す。
  論文  参考訳（メタデータ） (2022-10-24T12:22:25Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)

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

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