Fugu-MT 論文翻訳(概要): Three methods, one problem: Classical and AI approaches to no-three-in-line

論文の概要: Three methods, one problem: Classical and AI approaches to no-three-in-line

arxiv url: http://arxiv.org/abs/2512.11469v1
Date: Fri, 12 Dec 2025 11:12:42 GMT
ステータス: 翻訳完了
システム内更新日: 2025-12-15 15:48:11.742338
Title: Three methods, one problem: Classical and AI approaches to no-three-in-line
Title（参考訳）: 3つの方法、1つの問題:古典的アプローチとAIアプローチ
Authors: Pranav Ramanathan, Thomas Prellberg, Matthew Lewis, Prathamesh Dinesh Joshi, Raj Abhijit Dandekar, Rajat Dandekar, Sreedath Panat,
Abstract要約: No-Three-In-Line 問題では、3つのコリニア点を持たない n 個の格子で n 上に置ける最大点数を求める。線形プログラミング(ILP)のような古典的な手法は最適解を保証するが、グリッドサイズで指数関数的なスケーリングに直面している。本稿では,従来のアルゴリズムと比較して,古典最適化とAIアプローチの体系的比較を行った。
参考スコア（独自算出の注目度）: 3.959606080565717
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The No-Three-In-Line problem asks for the maximum number of points that can be placed on an n by n grid with no three collinear, representing a famous problem in combinatorial geometry. While classical methods like Integer Linear Programming (ILP) guarantee optimal solutions, they face exponential scaling with grid size, and recent advances in machine learning offer promising alternatives for pattern-based approximation. This paper presents the first systematic comparison of classical optimization and AI approaches to this problem, evaluating their performance against traditional algorithms. We apply PatternBoost transformer learning and reinforcement learning (PPO) to this problem for the first time, comparing them against ILP. ILP achieves provably optimal solutions up to 19 by 19 grids, while PatternBoost matches optimal performance up to 14 by 14 grids with 96% test loss reduction. PPO achieves perfect solutions on 10 by 10 grids but fails at 11 by 11 grids, where constraint violations prevent valid configurations. These results demonstrate that classical optimization remains essential for exact solutions while AI methods offer competitive performance on smaller instances, with hybrid approaches presenting the most promising direction for scaling to larger problem sizes.
Abstract（参考訳）: No-Three-In-Line問題(英語版)は、3つのコリナーを持たない n 個の格子で n 上に置ける最大点数を求め、組合せ幾何学における有名な問題を表している。 Integer Linear Programming (ILP)のような古典的な手法は最適なソリューションを保証するが、グリッドサイズで指数関数的なスケーリングに直面している。本稿では,従来のアルゴリズムと比較して,古典最適化とAIアプローチの体系的比較を行った。本稿では,この問題に対して初めてPatternBoost Transformer Learning and reinforcement Learning (PPO)を適用し,ILPと比較した。 ILPは19×19のグリッドで、PatternBoostは14×14のグリッドで、テスト損失は96%減少する。 PPOは10×10のグリッド上で完璧なソリューションを実現するが、11×11のグリッドでは失敗する。これらの結果は、AI手法がより小さなインスタンス上での競合性能を提供する一方で、古典的な最適化が正確なソリューションに不可欠であることを示し、ハイブリッドアプローチはより大きな問題サイズにスケールするための最も有望な方向を示す。

関連論文リスト

Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach [5.84228364962637]
本稿では,最適化問題を近似する効率的なアルゴリズムを学習するメタ最適化手法を提案する。我々は,学習方法の指数収束,近似保証,一般化境界を証明した。この手法は計算効率に優れ、高品質な近似を高速に生成し、既存の手法と比較して問題の大きさでスケールする。
論文参考訳（メタデータ） (2025-05-16T15:27:50Z)
Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文参考訳（メタデータ） (2024-11-04T15:17:19Z)
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)
Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文参考訳（メタデータ） (2023-07-17T20:11:56Z)
Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
本稿では,候補アルゴリズムの集合に有効な手法を提案する。内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。提案手法は,他のアルゴリズムのスコアを大幅に改善する。
論文参考訳（メタデータ） (2023-05-26T21:49:37Z)
Polynomial Optimization: Enhancing RLT relaxations with Conic Constraints [0.0]
円錐最適化は、非スケール問題に対するトラクタブルで保証されたアルゴリズムを設計するための強力なツールとして登場した。最適化問題に対するRLT緩和の強化について,9種類の制約を加えて検討する。我々は、これらの変種とその性能を、互いに、そして標準RCT緩和に関してどのように設計するかを示す。
論文参考訳（メタデータ） (2022-08-11T02:13:04Z)
Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
論文参考訳（メタデータ） (2021-01-25T01:49:10Z)
Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-12-04T00:26:56Z)
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)

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

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