Four Methods, One Problem: The No-Three-In-Line Problem

Motivation

• Known: No-Three-In-Line 문제는 n×n grid에서 세 점이 collinear하지 않도록 최대 개수의 점을 배치하는 조합기하학의 고전적 문제로, 2n의 trivial upper bound와 약 1.5n의 최선의 lower bound(Hall, Jackson, Sudbery, Wild), 그리고 Guy와 Kelly가 제안한 cn(c≈1.814)의 점근적 conjecture가 알려져 있다. 기존 CP-SAT/GPU 완전탐색은 symmetry pruning에 의존해 n≥60까지 도달했으나 pruning 없이는 n=19-20 수준에 머문다.
• Gap: ILP, transformer 기반 패턴 학습(PatternBoost), 강화학습(PPO), SciML 연속완화 방법을 동일 문제에 대해 체계적으로 비교한 선행 연구가 없었으며, 특히 PatternBoost의 collinearity 기반 제약 문제 적용과 PPO의 action masking 적용, SciML의 gradient flow 기반 접근이 이 문제에 시도된 바 없었다.
• Why: 이 비교 연구는 각 discrete-search 및 learning 기반 방법론이 조합기하학 문제에서 갖는 확장성(scalability)과 실패 양상을 규명함으로써, symmetry pruning 없이도 continuous-relaxation 기법이 학습 기반 solver의 도달 범위를 discrete-search 방법의 한계를 넘어 확장할 수 있음을 시사하여 향후 조합최적화 연구 방향에 실질적 지침을 제공한다.
• Approach: collinearity 제약을 line 단위로 집약한 ILP 정식화를 공통 기반으로 삼아, Gurobi 기반 정확 해법, GPT-2 스타일 decoder-only transformer를 이용한 PatternBoost, action masking을 적용한 PPO 강화학습, 그리고 문제를 연속 에너지 최소화로 재구성해 Apple M2 Metal GPU에서 gradient flow로 푸는 SciML 방법을 각각 구현해 성능을 비교한다.

Achievement

1. ILP의 최적성 입증: Gurobi를 이용한 ILP는 19×19 grid까지 provably optimal solution을 달성했다.
2. PatternBoost의 준최적 성능: PatternBoost는 14×14 grid까지 optimal을 달성했고, 15×15 grid에서는 최적값 30에 근접한 29점을 발견했다.
3. PPO의 한계 규명: PPO는 10×10 grid에서 완벽한 해를 찾았으나 11×11에서는 constraint violation으로 실패하여 강화학습 discrete-search의 한계를 보였다.
4. SciML의 확장성: symmetry pruning 없이 Apple M2 Metal 하드웨어에서 gradient flow 기반 SciML이 n=18까지 optimal 2n 구성을 여러 경우 발견하여 discrete-search 방법의 한계를 넘어섰으나, n=17에서는 10회 중 0회 성공(1개 seed만 재현), n=18에서는 9/10 성공하는 등 non-monotonic한 신뢰성을 보였다.

How

• ILP: n² 개의 이진 변수와 Θ(n⁴)개의 line 기반 선형 제약을 구성해(Algorithm 1) Gurobi의 branch-and-bound로 해결
• PatternBoost: grid cell을 토큰화하여 GPT-2 스타일 decoder-only transformer(4 layer, 4 head, hidden dim 64)로 next-token prediction을 학습, greedy saturation(Algorithm 2)으로 생성한 20,000개 초기 데이터와 fixed-capacity priority queue(TopPool, K=20,000)를 이용해 반복적으로 우수 패턴을 학습·생성
• PPO: actor-critic 구조(공유 512×2 MLP backbone)에 action masking을 적용하여 collinearity 제약을 위반하는 행동을 배제하며 정책을 학습
• SciML: 문제를 continuous energy minimisation으로 재구성하고 collinearity-penalty schedule α(n)을 적용한 gradient flow를 Apple M2(Metal) GPU에서 symmetry pruning 없이 수행

Originality

• No-Three-In-Line 문제에 대해 ILP, PatternBoost, PPO, SciML 네 가지 이질적 패러다임을 최초로 통합 비교한 체계적 연구
• PatternBoost를 collinearity 기반 제약 문제에 최초로 적용
• action masking을 적용한 PPO 에이전트를 No-Three-In-Line 문제에 최초로 적용
• 문제를 continuous energy minimisation으로 재구성하여 Apple Metal GPU 상에서 gradient flow로 해결하는 novel SciML 방법 제안

Limitation & Further Study

• SciML 방법의 성공률이 grid 크기에 따라 non-monotonic하게 나타나며(n=17에서 0/10, n=18에서 9/10), 재현성과 신뢰성에 대한 이론적 설명이 부족함
• PPO는 11×11 이상에서 constraint violation으로 실패하여 discrete-search 기반 강화학습의 확장성 한계가 명확히 규명되지 않음
• PatternBoost와 PPO 모두 상대적으로 작은 grid(≤15×15, ≤10×10)에서만 검증되어 대규모 문제에 대한 일반화 가능성이 불분명함
• 후속 연구로 SciML의 실패 모드에 대한 이론적 분석, 더 큰 n에서의 continuous-relaxation 방법 확장, 그리고 하이브리드(ILP+learning) 접근법 탐구가 필요함

Evaluation

총평: 네 가지 이질적 방법론을 하나의 조합기하학 문제에 대해 체계적으로 비교한 최초의 시도로서 학술적 가치가 크며, 특히 SciML의 continuous-relaxation 접근이 discrete-search 기반 학습 방법의 한계를 넘어설 수 있다는 시사점은 흥미롭지만, SciML의 non-monotonic한 신뢰성 문제에 대한 심층 분석이 보완된다면 더욱 완성도 높은 연구가 될 것이다.